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 $A$ of size $N$. Anthony can perform the following operation any number of times: change an element of $A$ to any arbitrarily large non-negative integer. Let the array $B$ be the prefix bitwise XOR array of $A$. Formally, $B_i=A_1\oplus A_2\oplus \cdots \oplus A_i$. Please tell Anthony the minimum number of operations to sort $B$ in non-decreasing order.

Constraints

$1\le N\le {10}^6$

$0\le A_i<2^{30}$

Subtask 1 [20%]

$1\le N\le {10}^3$

$0\le A_i<2^8$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains the integer $N$.

The next line contains $N$ space-separated integers, representing the array $A$.

Output Specification

Output the minimum number of operations to make $B$ nondecreasing.

Sample Input

3
2 2 4

Sample Output

1

Explanation for Sample

$1$ operation can be performed by changing the first element to $0$, making $B$ nondecreasing.