Vika and Wiki
Contest: Codeforces Round 885 (Div. 2)
Difficulty rating: 2400
Tags: binary search, bitmasks, combinatorics, divide and conquer, dp, math

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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]$$$.

Example input:
4
1 2 1 2

Example output:
2

Example input:
2
0 0

Example output:
0

Editorial:
Let's denote $$$next(i, delta) = (i + delta \bmod n) + 1$$$, and $$$a[cnt][i]$$$ represents the value of $$$a_i$$$ after $$$cnt$$$ operations.
First, let's observe that if the array becomes all zeros, it will always remain all zeros. Therefore, we need to find the first moment in time when the array becomes all zeros.
Furthermore, let's see how the array looks like after $$$2^t$$$ operations. We will prove by induction that $$$a[2^t][i] = a[0][i] \oplus a[0][next(i, 2^t)]$$$ for each $$$i$$$. Indeed, for $$$t = 0$$$, this is true by definition, and for $$$t \ge 1$$$:
$$$a[2^t][i] = a[2^{t-1}][i] \oplus a[2^{t-1}][next(i, 2^{t-1})] = a[0][i] \oplus a[0][next(i, 2^{t-1})] \oplus a[0][next(i, 2^{t-1})] \oplus a[0][next(i, 2^t)] = a[0][i] \oplus a[0][next(i, 2^t)]$$$.
Thus, $$$a[n][i] = a[2^k][i] = a[0][i] \oplus a[0][next(i, n)] = a[0][i] \oplus a[0][i] = 0$$$, which means that after $$$n$$$ steps, the array becomes all zeros.
Now, we want to find the minimum number of operations $$$c$$$ after which the array $$$a$$$ becomes all zeros, knowing that $$$c \in [0, n]$$$. Let's check that $$$c \le n / 2$$$, by explicitly constructing the array $$$a[n/2][i] = a[0][i] \oplus a[0][next(i, n / 2)]$$$. The condition $$$c \le n / 2$$$ is equivalent to all elements of the array $$$a[n/2][i]$$$ being zeros.
The algorithm can be summarized as follows:
Check if $$$a_i = a_{next(i, n/2)}$$$ for each $$$i$$$. If this is true, find the answer for the prefix of the array $$$a$$$ of length $$$n/2$$$. Otherwise, perform $$$n/2$$$ operations on the array $$$a$$$, specifically $$$a_i = a_i \oplus a_{next(i, n / 2)}$$$. Now, the array satisfies the condition $$$a_i = a_{next(i, n/2)}$$$ for each $$$i$$$, so we only need to find the answer for its prefix of size $$$n/2$$$ and add $$$n/2$$$ to it.
The overall complexity of the solution is $$$O(n)$$$.