题目背景

$\oplus$ 代表异或（xor）运算，运算规则为：

• 当只有一位比特参与运算时，$0\oplus0=0$，$0\oplus1=1$，$1\oplus0=1$，$1\oplus1=0$（相同为$0$，相异为$1$）；
• 当有多位比特参与运算时，对每位比特分别取异或运算，如 $0101\oplus 1011=1110$；

题目描述

给定一个长度为 $n$的序列$a_1,a_2,\dots,a_n$，求这个序列有多少个区间 $l\leq r$ 满足以下条件：

$$a_l + a_{l+1} + \dots +a_{r-1} +a_r =a_l \oplus a_{l+1} \oplus \dots \oplus a_{r-1} \oplus a_r $$

输入格式

• 第一行：单个整数表示 $n$
• 第二行：$n$ 个整数表示 $a_1,a_2,\dots,a_n$

输出格式

• 单个整数表示答案。

4
1 2 4 2

8

数据范围

• $30\%$ 的数据，$1\leq n\leq 100$
• $60\%$ 的数据，$1\leq n\leq 2000$
• $100\%$ 的数据，$1\leq n\leq 300,000$，$0 \leq a_i< 2^{30}$