最近,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]$$$。