I2. Insecure (Don't Know What For)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The RXA cryptosystem is the same in both problems. Skip to paragraph beginning with "Cindy" for the difference between the two problems.

Alice and Bob were attending a cryptography seminar in the province of Siquijor, where they learned about the famous RSA cryptosystem used for public-key encryption. Inspired by this, they decided to create their own cryptosystem which they called RXA.

Suppose Alice wants to send Bob a secret message $$$M$$$, which is a string—let $$$n$$$ be the length of this string. They have developed the following three-pass protocol.

First, Alice encodes the string $$$M$$$ into a (possibly very large) integer $$$m$$$ (by a process described below). Now, she communicates this integer $$$m$$$ to Bob by the following procedure.

Let $$$a \oplus b$$$ denote the bitwise XOR of two non-negative integers $$$a$$$ and $$$b$$$ (see Notes for an explanation).

  • Alice generates a secret non-negative integer $$$a$$$, then sends to Bob the value $$$x := a \oplus m$$$.
  • Bob also generates a secret non-negative integer $$$b$$$, and sends back to Alice the value $$$y := b \oplus x$$$.
  • Alice then sends back to Bob the value $$$z := a \oplus y$$$.
From here, we can show that Bob can retrieve the integer $$$m$$$, since $$$m = b \oplus z$$$. Since Bob also knows the encoding scheme, he can then retrieve the original string $$$M$$$.

Note that the only values that can be heard by the public are $$$x$$$, $$$y$$$, and $$$z$$$. The secret integers $$$a$$$ and $$$b$$$ are not revealed by Alice and Bob, not even to each other.

Cindy calls them both idiots, because this cryptographic scheme has a fatal flaw. The message $$$M$$$ can actually be retrieved by a malicious third party! In fact, not only can it be retrieved—it's actually super easy to do so.

To prove her point, she considers the following problem.

Let $$$v_1, v_2, \dots, v_n$$$ be an array of positive integers. There are $$$n(n-1)(n-2)$$$ triples $$$(i, j, k)$$$ such that $$$1 \leq i, j, k \leq n$$$ and $$$i \neq j$$$ and $$$i \neq k$$$ and $$$j \neq k$$$.

Let $$$m(i, j, k)$$$ be the value of $$$m$$$ recovered from Alice and Bob's scheme, if $$$x = v_i$$$ and $$$y = v_j$$$ and $$$z = v_k$$$. Cindy believes that it should be possible to find the sum of $$$m(i, j, k)$$$ across all $$$n(n-1)(n-2)$$$ such triples of $$$(i, j, k)$$$.

We believe her. Which is why we're making you solve this problem!

Input

The first line of input contains the integer $$$n$$$.

The second line contains $$$n$$$ space-separated integers $$$v_1, v_2, \cdots, v_n$$$.

Output

Output a single integer, the answer to the problem. Note that the answer can be quite large... beware integer overflow.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 3 \leq n \leq 150000 \\ \text{$0 \leq v_i \lt 2^{30}$ for each $i$} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & n \le 15 \\ \hline 2 & \mathbf{25} & n \le 200 \\ \hline 3 & \mathbf{25} & n \le 2000 \\ \hline 4 & \mathbf{25} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Example
Input
5
314 159 265 358 979
Output
33432
Note

The logical XOR accepts two values as input, each $$$0$$$ or $$$1$$$. It returns $$$1$$$ if the two inputs are different, and returns $$$0$$$ if the two inputs are the same.

The bitwise XOR between two non-negative integers is computed by writing both inputs in binary (using the same number of bits, adding padding leading zeros if necessary), and then performing a logical XOR on each corresponding pair of bits at the same place values. For example, $$$5 \oplus 9 = 12$$$. We write $$$5 = 0101_2$$$ and $$$9 = 1001_2$$$, then: 


0101
1001
====
1100
and $$$1100_2 = 12$$$.