D. Fantastic Three
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array of non-negative integers $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$. Count number of triplets $$$1 \le i \lt j \lt k \le n$$$, such that $$$(a_i \oplus a_j) \lt (a_j \oplus a_k)$$$, where $$$\oplus$$$ is an exclusive OR (XOR) operation.

Input

The first line contains a single integer $$$n$$$ — the number of elements in the array ($$$3 \le n \le 200\,000$$$).

The second line contains $$$n$$$ integer numbers $$$a_i$$$ — elements of the array ($$$0 \le a_i \le 10^{18}$$$).

Output

Output single integer — the number of triplets.

Scoring
SubtaskScoreConstraints
$$$1$$$$$$17$$$$$$n \le 100$$$
$$$2$$$$$$19$$$$$$n \le 3\,000$$$
$$$3$$$$$$18$$$$$$n \le 30\,000$$$, $$$a_i \le 50$$$
$$$4$$$$$$22$$$$$$n \le 30\,000$$$
$$$5$$$$$$24$$$No additional constraints
Examples
Input
3
0 1 2
Output
1
Input
4
0 1 2 3
Output
2
Input
5
6 1 17 3 11
Output
7
Input
10
0 1 2 3 4 5 6 7 8 9
Output
84