You are given an array \(A\) of even length \(N\) consisting of non-negative integers. You need to make each element of the array equal to zero, by doing some number of moves (possibly zero).

In a single move, you can choose two integers, \(l\) and \(r\), so \(1 \leq l \leq r \leq N\). Let \(x = A[l] ⊕ A[l+1] ⊕ A[l+2] ... A[r]\), where ⊕ represents xor operator. Then, replace the whole subarray with \(x\). In other words, assign \(A[i] = x\) for \(l ≤ i ≤ r\).

Print the minimum number of moves required to make the entire array zero.

Input format

The first line contains a single integer \(N\) – the length of array \(A\).
The next line contains \(N\) space-separated integers representing the elements of the array \(A\).

Output format
Output a single integer – the answer.

Constraints

\(1 \leq N \leq 10^6\\ \\0\leq A[i] \le 10^9\\ \\N\;is\;even\)