409040: GYM103426 D Fantastic Three

Memory Limit：512 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

D. Fantastic Threetime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are given an array of non-negative integers $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$. Count number of triplets $$$1 \le i < j < k \le n$$$, such that $$$(a_i \oplus a_j) < (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
ExamplesInput
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

Source/Category

加入题单

上一题 下一题 算法标签：