#1467. [YsOI2023] 区间翻转区间异或和

[YsOI2023] 区间翻转区间异或和

题目描述

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

符卡有特殊的魔法,可以把任意一个灵异区间翻转。具体来说,如果 [l,r][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$。

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

输入格式

第一行一个正整数 nn,表示数组长度。

第二行 nn 个非负整数 a1,a2,…,ana_1,a_2,\dots,a_n 表示整个数组。

输出格式

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

样例

3
1 1 1
2
4
3 1 2 3
2

题目来源:洛谷 P9533