9 weeks ago

John 910

Hyderabad

Avg CTC: 13lpa

Job Roles: Full Stack Developer, Java Developer,

Location: Mumbai, Bengaluru, Chennai, Hyderabad

Job link: Apply here

Question

Antony builds a monotonically increasing (According to Wikipedia: always increasing, or remaining constant but never decreasing) array(a) 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. Therefore, 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 array
2. Find the bitwise XOR of two elements selected
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.

For example, consider array a = [1, 2, 4, 6, 20]

1. Antony selects a0 and a1 i.e. 1 and 2
2. Finds their bitwise XOR 1 ⊕ 2 = 3
3. Remove 1, 2 from the array and insert 3 at their position.

Now the array becomes a = [3, 4, 6, 20]

1. Antony selects a0 and a1 i.e. 3 and 4
2. Finds their bitwise XOR 3 ⊕ 4 = 7
3. Removes 3, and 4 from the array and inserts 7 at their position

Finally, after two iterations array is not monotonically increasing anymore, a = [7, 6, 20].

As Antony has other tasks to complete, he wants to make as few iterations as feasible. Help Anthony find it, 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

5
1  2  4  6  20

Output

2

Input

3
1  2  3

Output

-1

Input

5
3  4  7  8  8 

Output

1

11 months ago

Manas 310

Bānswāra

Solution

• Observation 1 - It can be noted that if we have 3 continuous numbers which have the same MSB (most significant bit), i.e 3 continuous elements with MSB as 1 (we will take the highest bit of the 3rd number, since it is the biggest) will imply that if i take xor of the last 2 elements , it will become smaller than the first number as the MSB for these two would become 0 (1^1 = 0) and for the first number it will be 1. Note that we have 32 bits in an integer, and at max we want 2 continuous elements to have set bit as 1. Since we know that the array is monotonically increasing, these have to occur together. Worst case we can have only 64 length array (Each of the 32 bit is set for 2 number and then that bit becomes 0). Hence for any N > 64, the answer will have to be 1. Otherwise we can follow the method below to calculate.

• Observation 2 (For n <= 64) - Note that there will be an element at which the array is no more monotonically increasing, let's refer to this point as change point. If we can check for every element and figure out the minimum number of operations needed to make this point as the change point and take minimum of all the values, then we can get the final answer.

• Solution - If any point a[i] is the change point, the we need to take xor of elements occurring after a[i] such that the new element a[i+1] is smaller than a[i]. In other words, we would take xor of elements continuously occurring after a[i] till we have some element a[i+j] such that xor of all elements from a[i+1] to a[i+j] is less than a[i]. If we keep doing these operations for every element then the complexity will become n^3. Hence We will save the prefix xor of all elements for each elements, and as we start checking from the first element, we will xor the value of that element with every other element to remove it from the prefix. In other words, since x^x = 0, in any position if we have xor from a[0] till a[i] and we want to the xor from 'a[k] to a[i]' we need to just xor a[0] to a[i] with a[0] to a[k-1]. a[i]^a[i+j] = prefix[i+j] ^ prefix[i-1].

Using the above explanation we can find the answer in O(n^2) (for all n < = 64, other wise O(1)).