描述

现在有一个长度为 n 的数组 {a n ​ }，对于一个区间 [l,r]，如果区间中的所有元素 a l ​ ,a l+1 ​ ⋯,a r ​ 的异或和为 0，那么可以对整个数组进行操作，变为：a 1 ​ ,⋯,a l−1 ​ ,a r ​ ,a r−1 ​ ,⋯,a l+1 ​ ,a l ​ ,a r+1 ​ ,⋯,a n ​ ，即：把区间 [l,r] 的元素翻转顺序。

操作的次数是不限的，我们希望最终的数组里有尽量多的区间满足，区间中所有元素异或和为 0，问：这样的区间最多有多少个。

输入描述

从文件 xor.in 读入数据。

第一行一个整数 n。

第二行 n 个整数，代表 {a n ​ } 数组。

输出描述

输出到文件 xor.out。

输出一个整数，代表满足条件的区间数的最大值。

用例输入 1

4 3 1 2 3 用例输出 1

2 提示

测试点限制 对于 10% 的数据，n≤10； 对于 40% 的数据，n≤2000； 另有 10% 的数据，a i ​ 全部相等； 另有 10% 的数据，0≤a i ​ ≤2 10 ； 对于 100% 的数据，n≤10 5 ,0≤a i ​ ≤2 21 。