Background

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

Problem Description

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.

Input Format

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 Format

Output one integer in one line, representing the answer.

2
1 3 

7

10
114514 19 19 810 1477 44151 15260 369 2010 222

1396

Hint

Sample Explanation #1

As shown in the table below, the answer is $1 + 2 + 2 + 2 = 7$.

$i$	$j$	$ans$
$1$	$1$
	$2$	$2$
$2$	$1$
	$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		None	$40$

Translated by ChatGPT 5