题目描述

有一个长度为 $N$ 的整数序列 $A$。

找出满足以下条件的整数对 $(l, r)$ 的数量：

• $A_l\\ xor\\ A_{l+1}\\ xor\\ ...\\ xor\\ A_r = A_l\\ +\\ A_{l+1}\\ +\\ ...\\ +\\ A_r$

这里，$xor$ 表示按位异或。

XOR 的定义

整数 $c_1, c_2, ..., c_m$ 的 XOR 定义如下：

• 设 XOR 为 $X$。在 $X$ 的二进制表示中，当且仅当 $c_1, c_2, ...c_m$ 中有奇数个整数的二进制表示在 $2^k$ 位上为 $1$ 时，$2^k$ 位上的数字为 $1$；否则为 $0$。

例如，我们计算 $3$ 和 $5$ 的 XOR。$3$ 的二进制表示为 $011$，$5$ 的二进制表示为 $101$，所以 XOR 的二进制表示为 $110$，即 XOR 是 $6$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i < 2^{20}$
• 输入中的所有值都是整数。

输入

输入是标准输入提供的，格式如下：

$N$ $A_1$ $A_2$ $...$ $A_N$

输出

打印满足条件的整数对 $(l, r)$ 的数量。

示例输入 1

4
2 5 4 6

示例输出 1

5

明显有 $(l,r)=(1,1),(2,2),(3,3),(4,4)$ 满足条件。$(l,r)=(1,2)$ 也满足条件，因为 $A_1\\ xor\\ A_2 = A_1\\ +\\ A_2 = 7$。其他没有满足条件的整数对，所以答案是 $5$。

示例输入 2

9
0 0 0 0 0 0 0 0 0

示例输出 2

45

示例输入 3

19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1

示例输出 3

37