← 返回题目列表

Codeforces · 1848/F

F. 维卡和维基

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

最近,Vika 正在研究她最喜欢的互联网资源 - 维基百科。

在维基百科上,她读到了一个有趣的数学运算按位异或,用 $$$\oplus$$$ 表示。

维卡开始研究这个神秘操作的特性。为此,她采用一个由 $$$n$$$ 非负整数组成的数组 $$$a$$$,并同时对其所有元素应用以下运算:$$$a_i = a_i \oplus a_{(i+1) \bmod n}$$$。这里 $$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 的余数。数组的元素从$$$0$$$开始编号。

由于一次完整的研究执行上述操作是不够的,Vika 会重复这些操作,直到数组 $$$a$$$ 变为全零。

确定需要执行多少次上述操作才能使数组 $$$a$$$ 的所有元素为零。如果这一刻永远不会到来,则输出 $$$-1$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2^{20}$$$) - 数组 $$$a$$$ 的长度。

对于某个整数 $$$k$$$ ($$$0 \le k \le 20$$$),保证 $$$n$$$ 可以表示为 $$$2^k$$$。

第二行包含 $$$n$$$ 整数 $$$a_0, a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \le a_i \le 10^9$$$) - 数组 $$$a$$$ 的元素。

输出

输出一个数字 - 使数组 $$$a$$$ 的所有元素为零所需的最小操作数,或者如果数组 $$$a$$$ 永远不会变为零,则输出 $$$-1$$$。

示例

输入 #1

4
1 2 1 2

输出 #1

2

输入 #2

2
0 0

输出 #2

0

输入 #3

1
14

输出 #3

1

输入#4

8
0 1 2 3 4 5 6 7

输出#4

5

注意

在第一个示例中,经过一次操作后,数组 $$$a$$$ 将等于 $$$[3, 3, 3, 3]$$$。再经过一次运算,就等于$$$[0, 0, 0, 0]$$$。

在第二个示例中,数组 $$$a$$$ 最初仅由零组成。

在第三个示例中,经过一次操作后,数组 $$$a$$$ 将等于 $$$[0]$$$。