题目描述

给定一个长度为 ( N ) 的整数序列 ( $A = (A_1, \ldots, A_N)$ )。求以下表达式的值： $\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} (A_i \oplus A_{i+1} \oplus \ldots \oplus A_j$)

按位异或的说明

非负整数 ( A ) 和 ( B ) 的按位异或（XOR）记作 ( $A \oplus B$ )，定义如下：

在 ( $A \oplus B$ ) 的二进制表示中，当且仅当 ( A ) 和 ( B ) 的二进制表示中某一位只有一个为 1 时，该位为 1；否则为 0。

例如，( $3 \oplus 5 = 6$ )（二进制：( $011 \oplus 101 = 110$ ）。

一般地，( k ) 个整数 ( $p_1, \ldots, p_k$ ) 的按位异或定义为 ( $(\ldots((p_1 \oplus p_2) \oplus p_3) \oplus \ldots \oplus p_k)$ )。可以证明，这与 ( $p_1, \ldots, p_k$ ) 的顺序无关。

约束条件

• ( $2 \leq N \leq 2 \times 10^5$ )
• ( $1 \leq A_i \leq 10^8$ )
• 所有输入值为整数。

输入格式

输入通过标准输入给出，格式如下：

N
A_1 A_2 \ldots A_N

输出格式

输出答案。

样例

样例输入 1

3
1 3 2

样例输出 1

3

计算过程：

• ( $A_1 \oplus A_2 = 2$ )
• ( $A_1 \oplus A_2 \oplus A_3 = 0$ )
• ( $A_2 \oplus A_3 = 1$ )

因此答案是 ( 2 + 0 + 1 = 3 )。

样例输入 2

7
2 5 6 5 2 1 7

样例输出 2

83