Maximizing Spooky Intervals

You are given an integer array \(a\) of length \(n\). An interval \([l,r]\) is called a spooky interval if and only if

\[ \bigoplus_{i=l}^{r} a_i = 0, \]

Fuka has a special magic which can reverse any spooky interval. Specifically, if the interval \([l,r]\) is spooky then by applying the magic the segment \(a_l,a_{l+1},\dots,a_r\) is replaced by \(a_r,a_{r-1},\dots,a_l\); the rest of the array remains unchanged.

Fuka is allowed to use this magic arbitrarily many times, and she wants to maximize the total number of spooky intervals in the final array. In other words, she wants to rearrange the array (by a sequence of reversals on spooky intervals) so that the number of intervals \([l,r]\) with

[ \bigoplus_{i=l}^{r} a_i = 0 ]

is as large as possible. Can you help her compute the maximum possible number of spooky intervals?

Note: For an array \(b_1,b_2,\dots,b_n\) with prefix xor defined as \(S_0=0\) and \(S_i=b_1\oplus b_2\oplus\cdots\oplus b_i\) for \(1\le i\le n\), a subarray \([l, r]\) is spooky if and only if \(S_{l-1}=S_r\). Therefore, the total number of spooky intervals equals

[ \sum_{x}\binom{f(x)}{2}, ]

where \(f(x)\) denotes the frequency of \(x\) among the prefix xors. Under the allowed moves, you may rearrange the array arbitrarily as long as the multiset of elements is preserved. Thus, the problem reduces to the following observation:

You can arrange the array so that a long contiguous block of the prefix xors are equal. In particular, if you can form a block of length \(B\) (including the initial \(S_0=0\)) with constant value, then the number of spooky intervals obtained from that block is

[ \binom{B}{2} = \frac{B\cdot (B-1)}{2}. ]

How can you maximize \(B\)? Notice that if an element equal to \(0\) is appended, the prefix xor remains unchanged. Also, if you have a pair of nonzero equal numbers \(x\), then if you place them consecutively, say at positions \(i+1\) and \(i+2\), the prefix xors satisfy

[ S_i,; S_i\oplus x,; (S_i\oplus x)\oplus x = S_i. ]

Thus a pair of identical nonzero numbers, when placed consecutively, does not change the prefix xor. Suppose the original array has \(z\) zeros and for every nonzero number \(x\) the count \(c_x\). In an optimal arrangement, you can use all zeros and for each nonzero \(x\) you can use \(2\cdot\lfloor c_x/2\rfloor\) occurrences to maintain the prefix xor. Hence, you can obtain a block of

[ B = 1 + z + \sum_{x\neq 0}\lfloor c_x/2 \rfloor ]

elements (the initial 1 accounts for \(S_0\)). Therefore, the answer is

[ \frac{B\cdot (B-1)}{2}. ]

Given the array \(a\), compute and output this maximum number of spooky intervals.

inputFormat

The first line contains a single integer \(n\) (1 \(\le n \le\) 10⁵), denoting the length of the array.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (0 \(\le a_i \le\) 10⁹), representing the array.

outputFormat

Output a single integer: the maximum number of spooky intervals that can be obtained.

sample

5
0 1 1 2 2

6