Score : $450$ points

问题陈述

给定一个长度为 $N$ 的整数序列 $A=(A_1,\ldots,A_N)$。找出以下表达式的值：

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N (A_i \oplus A_{i+1}\oplus \ldots \oplus A_j)$。

关于按位异或的说明：非负整数 $A$ 和 $B$ 的按位异或，记作 $A \oplus B$，定义如下：

• 在 $A \oplus B$ 的二进制表示中，$2^k$（$k \geq 0$）位置的数字是 $1$ 当且仅当在 $A$ 和 $B$ 的二进制表示中 $2^k$ 位置的数字中恰好有一个是 $1$；否则，它是 $0$。

例如，$3 \oplus 5 = 6$（二进制：$011 \oplus 101 = 110$）。 一般来说，$k$ 个整数 $p_1, \dots, p_k$ 的按位异或定义为 $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$。可以证明这与 $p_1, \dots, p_k$ 的顺序无关。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given an integer sequence $A=(A_1,\ldots,A_N)$ of length $N$. Find the value of the following expression:

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N (A_i \oplus A_{i+1}\oplus \ldots \oplus A_j)$.

Notes on bitwise XOR The bitwise XOR of non-negative integers $A$ and $B$, denoted as $A \oplus B$, is defined as follows:

• In the binary representation of $A \oplus B$, the digit at the $2^k$ ($k \geq 0$) position is $1$ if and only if exactly one of the digits at the $2^k$ position in the binary representations of $A$ and $B$ is $1$; otherwise, it is $0$.

For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).
In general, the bitwise XOR of $k$ integers $p_1, \dots, p_k$ is defined as $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$. It can be proved that this is independent of the order of $p_1, \dots, p_k$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^8$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\ldots$ $A_{N}$

Output

Print the answer.

Sample Input 1

3
1 3 2

Sample Output 1

3

$A_1 \oplus A_2 = 2$, $A_1 \oplus A_2 \oplus A_3 = 0$, and $A_2 \oplus A_3 = 1$, so the answer is $2 + 0 + 1 = 3$.

Sample Input 2

7
2 5 6 5 2 1 7

Sample Output 2

83