Problem Description

Given an integer sequence $A=(A_1,\ldots,A_N)$ of length $ N $. Compute 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)$

The bitwise xor of non-negative integers $ A $ and $ B $, denoted $A\ \oplus\ B$, is defined as follows: - When $A\ \oplus\ B$ is written in binary, the digit in the $ 2^k $ place ($k\ \geq\ 0$) is $ 1 $ if exactly one of the digits in the $ 2^k $ place of $ A $ and $ B $ in binary is $ 1 $, otherwise it is $ 0 $.

For example, $3\ \oplus\ 5\ =\ 6$ (in binary: $011\ \oplus\ 101\ =\ 110$).
In general, the exclusive or 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)$, and it can be proven that this value is independent of the order of $p_1,\ \dots,\ p_k$.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
1 3 2

Sample Output #1

3

Sample Input #2

7
2 5 6 5 2 1 7

Sample Output #2

83

Notes/Hints

Constraints

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

Sample Explanation 1

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

见题面 Input 部分

见题面 Output 部分