Oracle OA-1 2022

Problem Description

Aaron is constructing a non-decreasing sequence seq (as defined: either strictly increasing or remaining the same, but never decreasing) of pebbles. Each element in the sequence represents the number of pebbles in a stack that Brian, his friend, has created. However, Aaron's mischievous younger brother, Tim, tries to disrupt this sequence. Instead of directly taking pebbles from the stacks, he uses the following method to alter the sequence:

• He repeatedly applies the following steps as long as the sequence has at least two stacks and the sequence remains non-decreasing:
  1. Select any two consecutive elements in the sequence.
  2. Calculate the bitwise XOR of the two chosen elements.
  3. Remove the two elements and insert the XOR result back into the sequence at their position.
• After each iteration, the size of the sequence decreases by one, and the process stops when the sequence has only one stack left.

Example:

Given the sequence seq = [1, 2, 4, 6, 20]:

• Tim selects seq[0] and seq[1], which are 1 and 2.
• He computes their bitwise XOR: 1 XOR 2 = 3.
• The elements 1 and 2 are replaced by 3 in the sequence. The sequence now becomes seq = [3, 4, 6, 20].
• Tim then selects seq[0] and seq[1], which are 3 and 4.
• He computes their XOR: 3 XOR 4 = 7.
• The sequence now becomes seq = [7, 6, 20], and the sequence is no longer non-decreasing.

Task:

Aaron, being busy with other activities, wants to make the fewest number of iterations possible. Help Aaron find the minimum number of iterations needed to break the pattern, or print -1 if it's not possible.

Input:

• The first line contains the size of the sequence, a single integer m (2 ≤ m ≤ 10^5).
• The second line consists of m integers seq[0], seq[1], ..., seq[m-1] (1 ≤ seq[i] ≤ 10^9), representing the sequence elements.
  Note that seq[i] <= seq[i+1] for all 0 ≤ i < m−1.

Output:

• Return a single integer representing the minimum number of iterations required. If it's not possible, 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