You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

Ysuperman 模板测试的数据结构题。

符卡可以是人名也可以是队名。

题目描述

符卡有一个长度为 $n$ 的整数数组 $a$，符卡认为一个区间 $[l,r]$ 是灵异区间当且仅当 $\bigoplus_{i=l}^ra_i=0$，或者说这个区间内所有数字异或起来刚好等于 $0$。

符卡有特殊的魔法，可以把任意一个灵异区间翻转。具体来说，如果 $[l,r]$ 区间是灵异区间，那么符卡就可以对这个区间使用魔法，整个数组就会变成 $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$。

现在符卡可以使用任意次数的魔法，符卡希望最后得到的数组的灵异区间数量能够尽可能多，你能告诉她最后最多有多少个灵异区间吗？

输入格式

第一行一个正整数 $n$，表示数组长度。

第二行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$ 表示整个数组。

输出格式

输出一行一个整数，表示符卡使用任意次魔法后灵异区间最多有多少个。

3
1 1 1

2

4
3 1 2 3

2

提示

样例 1 解释

无论符卡发动多少次魔法，数组都是 $1,1,1$，所以发不发动魔法都没有任何关系。灵异区间永远都是 $[1,2],[2,3]$ 两个。

样例 2 解释

这里给出可能的一种魔法发动方法。

选择灵异区间 $[1,3]$ 发动魔法，得到的新数组是 $2,1,3,3$，这个数组共有两个灵异区间，分别是 $[1,3]$ 和 $[3,4]$。

可以证明答案无法超过 $2$。

数据范围

对于前 $20\%$ 的数据，保证 $n\le 10$。

对于前 $40\%$ 的数据，保证 $n\le 2000$。

另有 $10\%$ 的数据，保证 $a_i$ 全部相等。

另有 $10\%$ 的数据，保证 $a_i$ 只有两种可能的取值。

另有 $10\%$ 的数据，保证 $0\le a_i<2^{10}$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^5$，$0\le a_i< 2^{20}$。

彩蛋

灵异区间的名字其实是“零异（或）区间”的谐音。