XOR-gun
Contest: Technocup 2021 - Elimination Round 2
Difficulty rating: 2000
Tags: bitmasks, brute force, constructive algorithms

Arkady owns a non-decreasing array $$$a_1, a_2, \ldots, a_n$$$. You are jealous of its beauty and want to destroy this property. You have a so-called XOR-gun that you can use one or more times.

In one step you can select two consecutive elements of the array, let's say $$$x$$$ and $$$y$$$, remove them from the array and insert the integer $$$x \oplus y$$$ on their place, where $$$\oplus$$$ denotes the bitwise XOR operation. Note that the length of the array decreases by one after the operation. You can't perform this operation when the length of the array reaches one.

For example, if the array is $$$[2, 5, 6, 8]$$$, you can select $$$5$$$ and $$$6$$$ and replace them with $$$5 \oplus 6 = 3$$$. The array becomes $$$[2, 3, 8]$$$.

You want the array no longer be non-decreasing. What is the minimum number of steps needed? If the array stays non-decreasing no matter what you do, print $$$-1$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the initial length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array. It is guaranteed that $$$a_i \le a_{i + 1}$$$ for all $$$1 \le i < n$$$.

Output format:
Print a single integer — the minimum number of steps needed. If there is no solution, print $$$-1$$$.

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

Note:
In the first example you can select $$$2$$$ and $$$5$$$ and the array becomes $$$[7, 6, 8]$$$.

In the second example you can only obtain arrays $$$[1, 1]$$$, $$$[3, 3]$$$ and $$$[0]$$$ which are all non-decreasing.

In the third example you can select $$$1$$$ and $$$2$$$ and the array becomes $$$[3, 4, 6, 20]$$$. Then you can, for example, select $$$3$$$ and $$$4$$$ and the array becomes $$$[7, 6, 20]$$$, which is no longer non-decreasing.

Example input:
4
2 5 6 8

Example output:
1

Example input:
3
1 2 3

Example output:
-1

Editorial:
First let's compute array $$$b_1, b_2, \ldots, b_n$$$, where $$$b_i$$$ is the index of the highest bit equal to $$$1$$$ in the binary notation of $$$a_i$$$. The statement says $$$b_i \le b_{i + 1}$$$. These values can be computed by dividing the given numbers by $$$2$$$ until they are zero.
Note that if for a given $$$i$$$ the equality $$$b_{i - 1} = b_i = b_{i + 1} = t$$$ holds, then we can apply an operation to $$$a_i$$$ and $$$a_{i + 1}$$$, and the resulting integer is smaller than $$$a_{i - 1}$$$. Indeed, in $$$a_{i - 1}$$$ the highest bit set is $$$t$$$, but in $$$a_i \oplus a_{i + 1}$$$ the $$$t$$$-th and higher bits are zeros. That means if there is such an $$$i$$$ (it is easy to check in a single linear pass), then the answer is $$$1$$$.
Now note that if there is no such $$$i$$$, then the size of the array $$$n$$$ is not bigger than $$$2 \cdot \left(\lfloor\log_2{10^9}\rfloor + 1\right) = 60$$$! Indeed, there are no more than two integers with the same highest bit set. It is much easier to solve the problem in such constraints.
Consider some solution. In the final array, let's denote it as $$$c$$$, there is $$$i$$$ such that $$$c_i > c_{i + 1}$$$. Note that each element of the final array is equal to XOR of some subsegment of the initial array, and each element of the initial array belongs to exactly one such subsegment. Let this subsegment for $$$c_i$$$ be $$$a_l, a_{l + 1}, \ldots, a_m$$$, and for $$$c_{i + 1}$$$ be $$$a_{m + 1}, a_{m + 2}, \ldots, a_r$$$. Then it's clear that to find an optimal solution it is enough to loop through all possible values of $$$l$$$, $$$m$$$, and $$$r$$$ and check whether XOR of all elements of the left subsegment is larger than XOR of all elements of the right subsegment. If this inequality holds, update answer with value $$$r - l - 1$$$. The complexity of this part is $$$O(n^3)$$$ or $$$O(n^4)$$$ depending on implementation.