Oracle OA 2022 - Min XOR Array Break

Antony builds a monotonically increasing array a (According to Wikipedia: always increasing, or remaining constant but never decreasing) of a stack of pebbles. Each element in the array denotes the size of the pebble stack that Akbar built. However, a cheeky youngster named Antony, his younger brother, tries to break the pattern. Instead of directly removing stones from one of the stacks and breaking the pattern, he uses the following algorithm on the array a to do it.

Repeat until the array has at least two elements (stacks) and is monotonically increasing:

1. Select any two consecutive elements in the array.
2. Find the bitwise XOR of the two selected elements.
3. Remove the two elements and insert the value found in step 2 at their position.

It is important to note that the array size is reduced by one after each iteration, and the algorithm stops once the array size becomes 1.

Example:

Consider array a = [1, 2, 4, 6, 20]:

1. Antony selects a[0] and a[1] i.e. 1 and 2.
2. Finds their bitwise XOR: ( 1 XOR 2 = 3 ).
3. Removes 1 and 2 from the array and inserts 3 at their position.
   • Now the array becomes a = [3, 4, 6, 20].
4. Antony selects a[0] and a[1] i.e. 3 and 4.
5. Finds their bitwise XOR: ( 3 XOR 4 = 7 ).
6. Removes 3 and 4 from the array and inserts 7 at their position.

Finally, after two iterations, the array is no longer monotonically increasing: a = [7, 6, 20].

Task:

As Antony has other tasks to complete, he wants to make as few iterations as possible. Help Antony find the minimum number of iterations, or print -1 if it is impossible to do so.

Input:

• The first line contains the size of the array, a single integer n (2 ≤ n ≤ 10^5).
• The second line consists of n integers a0, a1, a2, ...... an-1 (1 ≤ ai ≤ 10^9), the elements of the array.
• Note that ai ≤ ai+1 for all 0 ≤ i < n−1.

Output:

Return a single integer with the minimum number of iterations required. If it is impossible, return -1.

Examples:

Input 1:

5
1 2 4 6 20

Output 1:

2

Input 2:

3
1 2 3

Output 2:

-1

Input 3:

5
3 4 7 8 8

Output 3:

1