D. Fantastic Three
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив из целых неотрицательных чисел $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$. Найдите количество троек чисел $$$1 \le i \lt j \lt k \le n$$$, таких что $$$(a_i \oplus a_j) \lt (a_j \oplus a_k)$$$, где $$$\oplus$$$ — это операция побитового исключающего ИЛИ (XOR).

Входные данные

В первой строке дано одно целое число $$$n$$$ — количество элементов в массиве ($$$3 \le n \le 200\,000$$$).

Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ — элементы массива ($$$0 \le a_i \le 10^{18}$$$).

Выходные данные

Выведите одно целое число — количество искомых троек.

Система оценки
ПодзадачаБаллыОграничения
$$$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$$$Без дополнительных ограничений
Примеры
Входные данные
3
0 1 2
Выходные данные
1
Входные данные
4
0 1 2 3
Выходные данные
2
Входные данные
5
6 1 17 3 11
Выходные данные
7
Входные данные
10
0 1 2 3 4 5 6 7 8 9
Выходные данные
84