Background

A data structure problem for Ysuperman template testdata.

The name “符卡 (Fuka)” can be a person’s name or a team name.

Problem Description

Fuka has an integer array $a$ of length $n$. Fuka says an interval $[l,r]$ is a “spooky interval” if and only if $\bigoplus_{i=l}^r a_i = 0$, that is, the XOR of all numbers in this interval is exactly $0$.

Fuka has special magic that can reverse any spooky interval. Specifically, if interval $[l,r]$ is a spooky interval, then Fuka can use magic on it, and the whole array becomes $a_1,a_2,\dots,a_{l-1},a_r,a_{r-1},\dots,a_l,a_{r+1},a_{r+2}\dots,a_n$.

Now Fuka can use magic any number of times. She wants the final array to have as many spooky intervals as possible. Can you tell her what the maximum possible number of spooky intervals is?

Input Format

The first line contains a positive integer $n$, the length of the array.

The second line contains $n$ non-negative integers $a_1,a_2,\dots,a_n$, representing the entire array.

Output Format

Output one line with one integer, the maximum possible number of spooky intervals after Fuka uses magic any number of times.

3
1 1 1

2

4
3 1 2 3

2

Hint

Explanation for Sample 1

No matter how many times Fuka uses magic, the array is always $1,1,1$, so using magic or not makes no difference. The spooky intervals are always exactly two: $[1,2]$ and $[2,3]$.

Explanation for Sample 2

One possible way to use the magic is given here.

Choose the spooky interval $[1,3]$ and use magic. The new array is $2,1,3,3$. This array has two spooky intervals: $[1,3]$ and $[3,4]$.

It can be proven that the answer cannot exceed $2$.

Constraints

For the first $20\%$ of the data, $n \le 10$.

For the first $40\%$ of the data, $n \le 2000$.

Another $10\%$ of the data guarantees that all $a_i$ are equal.

Another $10\%$ of the data guarantees that $a_i$ can take only two possible values.

Another $10\%$ of the data guarantees that $0 \le a_i < 2^{10}$.

For $100\%$ of the data, $1 \le n \le 10^5$ and $0 \le a_i < 2^{20}$.

Easter Egg

The name “spooky interval” is actually a pun on “zero XOR interval.”

Translated by ChatGPT 5