Pairwise XOR Sum

Given a sequence of length \(N\) with elements \(A_1, A_2, \ldots, A_N\), compute the total sum of the XOR of every pair of distinct elements. In other words, calculate:

$$\sum_{1 \le i < j \le N} \left(A_i \oplus A_j\right)$$

where \(\oplus\) denotes the bitwise XOR operation.

inputFormat

The first line contains an integer \(N\) (\(1 \le N \le 10^5\)), indicating the number of elements in the sequence. The second line contains \(N\) space-separated integers \(A_1, A_2, \ldots, A_N\).

outputFormat

Output a single integer representing the sum of XOR for every unique pair of elements, i.e.,

$$\sum_{1 \le i < j \le N} \left(A_i \oplus A_j\right)$$

sample

3
1 2 3

6