← 返回题目列表

Codeforces · 1415/D

D. 异或枪

中文机器翻译题面 查看原题

Arkady 拥有一个非递减数组 $$$a_1, a_2, \ldots, a_n$$$。你嫉妒它的美丽并想毁掉它。您有一把所谓的“异或枪”,可以使用一次或多次。

在一步中,您可以选择数组中的两个连续元素,例如 $$$x$$$ 和 $$$y$$$,将它们从数组中删除并在其位置插入整数 $$$x \oplus y$$$,其中 $$$\oplus$$$ 表示按位异或运算。请注意,操作后数组的长度减一。当数组长度达到1时,不能执行此操作。

例如,如果数组为$$$[2, 5, 6, 8]$$$,则可以选择$$$5$$$和$$$6$$$并将其替换为$$$5 \oplus 6 = 3$$$。该数组变为 $$$[2, 3, 8]$$$。

您希望数组不再是非递减的。需要的最少步骤是多少?如果无论您做什么,数组都保持不递减,则打印 $$$-1$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 数组的初始长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。对于所有$$$1 \le i < n$$$,保证$$$a_i \le a_{i + 1}$$$。

输出

打印一个整数——所需的最少步骤数。如果无解,则打印$$$-1$$$。

示例

输入 #1

4
2 5 6 8

输出 #1

1

输入 #2

3
1 2 3

输出 #2

-1

输入 #3

5
1 2 4 6 20

输出 #3

2

注意

在第一个示例中,您可以选择 $$$2$$$ 和 $$$5$$$,数组将变为 $$$[7, 6, 8]$$$。

在第二个示例中,您只能获取数组 $$$[1, 1]$$$、$$$[3, 3]$$$ 和 $$$[0]$$$,它们都是非递减的。

在第三个示例中,您可以选择 $$$1$$$ 和 $$$2$$$,数组将变为 $$$[3, 4, 6, 20]$$$。然后,例如,选择 $$$3$$$ 和 $$$4$$$,数组就变成 $$$[7, 6, 20]$$$,不再是非递减的。