题目描述

本题中，我们用 $\oplus$ 表示 按位异或 符号。

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，如果一对下标对 $(i, j)$ 同时满足如下两个条件，则我们称下标对 $(i, j)$ 为一对”快乐下标对”。

1. $i \lt j$ 且 $j - i + 1$ 是偶数；
2. 令 $mid = \frac{l + r - 1}{2}$，则 $a_l \oplus a_{l+1} \oplus \ldots \oplus a_{mid} = a_{mid+1} \oplus a_{mid+2} \oplus \ldots \oplus a_r$

换句话说，如果数列 $a$ 中存在一段长度为偶数的连续子序列，这个连续子序列以 $a_i$ 开头，以 $a_j$ 结尾，且该连续子序列中前一半元素的异或和等于后一半元素的异或和，则我们称下标对 $(i, j)$ 为一对快乐下标对。

求：数列 $a$ 中存在多少对快乐下标对？

输入格式

第一行，一个整数 $n(2 \le n \le 3 \cdot 10^5)$，表示数列长度。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(0 \le a_i \lt 2^{20})$，两两之间以一个空格分隔。

输出格式

输出一个整数，表示数列 $a$ 中存在的快乐下标对数量。

5
1 2 3 4 5

1

6
3 2 2 3 7 6

3

说明/提示

样例解释

样例1：存在 $1$ 对快乐下标对：$(2, 5)$，因为 $2 \oplus 3 = 4 \oplus 5 = 1$

样例2：存在 $3$ 对快乐下标对：$(2, 3)$，$(1, 4)$ 和 $(3, 6)$

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 30; a_i \lt 2^5$
• 对于 $60\%$ 的数据，$n \le 3000; a_i \lt 2^{10}$
• 对于 $100\%$ 的数据，$2 \le n \le 3 \cdot 10^5; 0 \le a_i \lt 2^{20}$