P10114 [LMXOI Round 1] Size

On a pitch-dark night, the witch took LMX away. HQZ, in order to save LMX, must complete the task given by the witch.

The witch gives a sequence $d$ of length $n$. The witch wants to compute: $$\sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}{((d_i\oplus d_j)+(d_i \otimes d_j))}$$ Here, $\oplus$ is defined as the number of $1$ bits in the binary representation of the sum of two numbers in binary addition, and $\otimes$ is defined as the number of $1$ bits in the binary representation of the difference between the larger number and the smaller number.

The first line contains an integer $n$, the length of the sequence. The second line contains $n$ non-negative integers, representing the sequence $d$.

Output one integer in one line, representing the answer.

**Sample Explanation #1** As shown in the table below, the answer is $1 + 2 + 2 + 2 = 7$. | $i$ | $j$ | $ans$ | | :-----: | :-----: | :-------: | | $1$ | $1$ | $1$ | | $1$ | $2$ | $2$ | | $2$ | $1$ | $2$ | | $2$ | $2$ | $2$ | For $100\%$ of the testdata, it is guaranteed that $1 \le n\le 2\times 10^6,\sum\limits d_i\le5\times10^7$。 ## Constraints | Subtask ID | $n$ | Special Property | Score | | :--------: | :------------------: | :-------------------------: | :--: | | Subtask #1 | $\le 2\times10^6 $ | $d_i =1$ | $10$ | | Subtask #2 | $\le 5000$ | None | $20$ | | Subtask #3 | $\le 2\times 10^6$ | $d_i$ is a power of $2$ | $30$ | | Subtask #4 | $\le 2\times 10^6$ | None | $40$ | Translated by ChatGPT 5