Planet X3

Time limit1sMemory limit192 MB

Summary

Given up to a million numbers, compute the sum over all pairs of the XOR of their values by counting set bits per bit position.

Level: Medium4 of 10
Topics: Bit manipulation, Math, Combinatorics
Solved: No attempts yet

Problem

Sanggeun visited the alien Planet X3 on an elementary school graduation trip. Every inhabitant of this planet has a natural number as a name, and every pair of inhabitants knows each other.

The affinity between two inhabitants is computed from their names in binary. Pad the shorter binary representation with leading zeroes so that the two lengths match. For each bit position, write 0 if the two bits are the same and 1 if they are different. The decimal value of the resulting binary number is their affinity.

For 10 and 19, the affinity is 25.

1 0 0 1 1 = 19
0 1 0 1 0 = 10
--------------
1 1 0 0 1 = 25

The value of Planet X3 is the sum of the affinities over all unordered pairs of distinct inhabitants. Given the inhabitants' names, compute the value of the planet.

Input

The first line contains the number of inhabitants, N. (1 <= N <= 1,000,000)

Each of the next N lines contains one inhabitant's name. Every name is a natural number between 1 and 1,000,000, inclusive.

Output

Print the value of Planet X3 on the first line.

Examples3

Example 1
Input
```
2
19
10
```
Expected output
```
25
```
Example 2
Input
```
3
7
3
5
```
Expected output
```
12
```
Example 3
Input
```
5
9
13
1
9
6
```
Expected output
```
84
```