Вам дан массив из целых неотрицательных чисел $$$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
