Problem Description

Given a sequence $A_1, A_2, \cdots, A_N$, compute

$$\sum_{1\le i\le j\le N} A_i\oplus A_{i+1}\oplus\cdots\oplus A_j$$

where $\bigoplus$ denotes bitwise XOR.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$.

Output Format

Output a single integer: the value of the expression.

2
1 2

6

Hint

• For $60\%$ of the testdata, $1 \le N \le 10^3$.
• For $100\%$ of the testdata, $1 \le N \le 10^5$, $0 \le A_i \le 10^9$.

Translated by ChatGPT 5