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~ ~...~ ~\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.