310540: CF1848F. Vika and Wiki

F. Vika and Wikitime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Recently, Vika was studying her favorite internet resource - Wikipedia.

On the expanses of Wikipedia, she read about an interesting mathematical operation bitwise XOR, denoted by $\oplus$.

Vika began to study the properties of this mysterious operation. To do this, she took an array $a$ consisting of $n$ non-negative integers and applied the following operation to all its elements at the same time: $a_i = a_i \oplus a_{(i+1) \bmod n}$. Here $x \bmod y$ denotes the remainder of dividing $x$ by $y$. The elements of the array are numbered starting from $0$.

Since it is not enough to perform the above actions once for a complete study, Vika repeats them until the array $a$ becomes all zeros.

Determine how many of the above actions it will take to make all elements of the array $a$ zero. If this moment never comes, output $-1$.

Input

The first line contains a single integer $n$ ($1 \le n \le 2^{20}$) - the length of the array $a$.

It is guaranteed that $n$ can be represented as $2^k$ for some integer $k$ ($0 \le k \le 20$).

The second line contains $n$ integers $a_0, a_1, a_2, \dots, a_{n-1}$ ($0 \le a_i \le 10^9$) - the elements of the array $a$.

Output

Output a single number - the minimum number of actions required to make all elements of the array $a$ zero, or $-1$ if the array $a$ will never become zero.

ExamplesInput

4
1 2 1 2

Output

2

Input

2
0 0

Output

0

Input

1
14

Output

1

Input

8
0 1 2 3 4 5 6 7

Output

5

Note

In the first example, after one operation, the array $a$ will become equal to $[3, 3, 3, 3]$. After one more operation, it will become equal to $[0, 0, 0, 0]$.

In the second example, the array $a$ initially consists only of zeros.

In the third example, after one operation, the array $a$ will become equal to $[0]$.

题目大意：
维卡正在研究她最喜欢的互联网资源 - 维基百科。在维基百科的广袤领域中，她了解到了一种有趣的数学运算——按位异或（bitwise XOR），用符号 $$$\oplus$$$ 表示。维卡开始研究这个神秘运算的性质。为此，她取了一个由非负整数组成的数组 $a$，并对数组的所有元素同时应用以下操作：$$$a_i = a_i \oplus a_{(i+1) \bmod n}$$$. 这里的 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。数组元素从 $0$ 开始编号。由于仅执行一次上述操作不足以完成研究，维卡会重复这些操作，直到数组 $a$ 的所有元素都变为零。确定需要多少次上述操作才能使数组 $a$ 的所有元素变为零。如果这一刻永远不会到来，输出 $-1$。

输入输出数据格式：
输入：
- 第一行包含一个整数 $n$ ($1 \le n \le 2^{20}$) —— 数组 $a$ 的长度。
- 第二行包含 $n$ 个整数 $a_0, a_1, a_2, \dots, a_{n-1}$ ($0 \le a_i \le 10^9$) —— 数组 $a$ 的元素。

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

注意：
- 在第一个示例中，经过一次操作后，数组 $a$ 将变为 $[3, 3, 3, 3]$。再经过一次操作后，它将变为 $[0, 0, 0, 0]$。
- 在第二个示例中，数组 $a$ 最初只包含零。
- 在第三个示例中，经过一次操作后，数组 $a$ 将变为 $[0]$。题目大意： 维卡正在研究她最喜欢的互联网资源 - 维基百科。在维基百科的广袤领域中，她了解到了一种有趣的数学运算——按位异或（bitwise XOR），用符号 $$$\oplus$$$ 表示。维卡开始研究这个神秘运算的性质。为此，她取了一个由非负整数组成的数组 $a$，并对数组的所有元素同时应用以下操作：$$$a_i = a_i \oplus a_{(i+1) \bmod n}$$$. 这里的 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。数组元素从 $0$ 开始编号。由于仅执行一次上述操作不足以完成研究，维卡会重复这些操作，直到数组 $a$ 的所有元素都变为零。确定需要多少次上述操作才能使数组 $a$ 的所有元素变为零。如果这一刻永远不会到来，输出 $-1$。 输入输出数据格式： 输入： - 第一行包含一个整数 $n$ ($1 \le n \le 2^{20}$) —— 数组 $a$ 的长度。 - 第二行包含 $n$ 个整数 $a_0, a_1, a_2, \dots, a_{n-1}$ ($0 \le a_i \le 10^9$) —— 数组 $a$ 的元素。 输出： - 输出一个数字 —— 使数组 $a$ 的所有元素变为零所需的最小操作数，如果数组 $a$ 永远不会变为零，则输出 $-1$。 注意： - 在第一个示例中，经过一次操作后，数组 $a$ 将变为 $[3, 3, 3, 3]$。再经过一次操作后，它将变为 $[0, 0, 0, 0]$。 - 在第二个示例中，数组 $a$ 最初只包含零。 - 在第三个示例中，经过一次操作后，数组 $a$ 将变为 $[0]$。