Problem Background

On a dark night, a witch abducted LMX, and HQZ is on a mission to rescue LMX by completing tasks given by the witch.

Problem Description

The witch provides a sequence \( d \) of length \( n \). She wants to compute:

\[ \sum_{i=1}^{n} \sum_{j=1}^{n} \left( (d_i \oplus d_j) + (d_i \otimes d_j) \right) \]

Here, \( \oplus \) represents the number of 1s in the binary sum of two numbers, and \( \otimes \) represents the number of 1s in the binary difference where the larger number is subtracted from the smaller.

Input Format

A single line containing an integer \( n \), the length of the sequence.

The second line contains \( n \) non-negative integers, representing the sequence \( d \).

Output Format

A single line containing an integer, the answer.

Sample Input and Output

Sample Input #1

2
1 3

Sample Output #1

7

Sample Input #2

10
114514 19 19 810 1477 44151 15260 369 2010 222

Sample Output #2

1396

Notes

Sample Explanation #1

As shown in the table below, the answer is \( 1 + 2 + 2 + 2 = 7 \).

For \( 100\% \) of the data, it is guaranteed that \( 1 \le n \le 2 \times 10^6 \) and \( \sum d_i \le 5 \times 10^7 \).

见题面 Input 部分

见题面 Output 部分