Sasha 喜欢编程。有一次,在一场漫长的比赛中,萨沙觉得自己有点累,需要放松一下。所以他做到了。但由于萨沙不是一个普通人,所以他更喜欢异常放松。闲暇时,Sasha 喜欢解决未解决的问题,因为解决问题非常有用。
因此,Sasha 决定解决以下问题:
你有一个数组 $$$a$$$ ,其中包含 $$$n$$$ 整数。您需要计算有趣的对 $$$(l, r)$$$ $$$(l \leq r)$$$ 的数量。要检查 $$$(l, r)$$$ 是否是有趣的对,请取 $$$mid = \frac{l + r - 1}{2}$$$,然后如果 $$$r - l + 1$$$ 是偶数且 $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_{mid} = a_{mid + 1} \oplus a_{mid + 2} \oplus \ldots \oplus a_r$$$,那么这对就很有趣了。换句话说,从$$$l$$$到$$$r$$$的子数组左半部分的元素$$$\oplus$$$应该等于右半部分的元素$$$\oplus$$$。请注意,$$$\oplus$$$ 表示按位异或运算。
是时候继续解决比赛了,所以莎莎要求你解决这个任务。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 数组的大小。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{20}$$$) — 数组本身。
输出
打印一个整数——有趣对的数量。您应该仅考虑 $$$r - l + 1$$$ 为偶数的对。
示例
输入 #1
5 1 2 3 4 5
输出 #1
1
输入 #2
6 3 2 2 3 7 6
输出 #2
3
输入 #3
3 42 4 2
输出 #3
0
注意
像Sasha一样酷,解决问题!
在第一个示例中,唯一有趣的对是 $$$(2, 5)$$$,如 $$$2 \oplus 3 = 4 \oplus 5 = 1$$$。
在第二个示例中,有趣的对是 $$$(2, 3)$$$、$$$(1, 4)$$$ 和 $$$(3, 6)$$$。
在第三个示例中,没有有趣的对。