Counting Pairs

Time limit1sMemory limit2048 MB

Summary

Count pairs (i, j) where A_i and A_j never both have a 1 at the same even bit position (bits 0, 2, 4, ...), which is exactly when the base-2 and base-4 results match.

Level: Medium6 of 10
Topics: Bit manipulation, Dynamic programming
Solved: No attempts yet

Problem

Consider the binary operator $\oplus_b(x, y)$ defined for $b \in \{2, 4\}$ as follows. First, convert both $x$ and $y$ into base $b$ . Then, for each corresponding digit pair, the resulting digit is the sum of the digit pair modulo $b$ . Finally, convert the result back to base ten. Note that $\oplus_2$ is the bitwise XOR operator.

For instance, $\oplus_4(18, 7) = 21$ . The base four representations of 18 and 7 are $(102)_4$ and $(013)_4$ . Adding each digit pair gives $(111)_4$ , which is 21 in base ten.

You are given a list of $N$ integers, $A_1, A_2, \dots, A_N$ . Count the pairs $(i, j)$ with $1 \le i < j \le N$ such that $\oplus_2(A_i, A_j) = \oplus_4(A_i, A_j)$ .

Input

The first line contains an integer $N$ ( $2 \le N \le 200000$ ). The second line contains $N$ integers $A_1, A_2, \dots, A_N$ ( $0 \le A_i \le 10^{12}$ ).

Output

Print a single integer, the number of pairs $(i, j)$ such that $1 \le i < j \le N$ and $\oplus_2(A_i, A_j) = \oplus_4(A_i, A_j)$ .

Examples4

Example 1
Input
```
5
2 2 0 1 3
```
Expected output
```
9
```
Example 2
Input
```
2
17 13
```
Expected output
```
0
```
Example 3
Input
```
10
13 7 29 4 18 0 4 21 12 20
```
Expected output
```
14
```
Example 4
Input
```
10
0 0 0 0 0 0 0 0 0 0
```
Expected output
```
45
```