Sum of XOR of All Subarrays

Given a sequence of integers \(A_1, A_2, \cdots, A_N\), your task is to compute the value of

\[ S = \sum_{1 \le i \le j \le N} (A_i \oplus A_{i+1} \oplus \cdots \oplus A_j), \]

where \(\oplus\) denotes the bitwise XOR operation. You are given the integer \(N\) followed by \(N\) integers.

inputFormat

The first line contains an integer \(N\) \( (1 \le N)\). The second line contains \(N\) space-separated integers representing the sequence \(A_1, A_2, \cdots, A_N\).

outputFormat

Output a single integer denoting the sum \(S = \sum_{1 \le i \le j \le N} (A_i \oplus A_{i+1} \oplus \cdots \oplus A_j)\).

sample

3
1 2 3

10