Anthony is obsessed with sorting algorithms. After mastering a couple different sorting algorithms, he is now learning how to solve more unconventional sorting problems. Initially, there is an array of size
. Anthony can perform the following operation any number of times: change an element of
to any arbitrarily large non-negative integer. Let the array
be the prefix bitwise XOR array of
. Formally,
. Please tell Anthony the minimum number of operations to sort
in non-decreasing order.
Constraints
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
Input Specification
The first line contains the integer .
The next line contains space-separated integers, representing the array
.
Output Specification
Output the minimum number of operations to make nondecreasing.
Sample Input
3
2 2 4
Sample Output
1
Explanation for Sample
operation can be performed by changing the first element to
, making
nondecreasing.
Comments