«Плотину надо поднять. Рычагом. Я его дам.Канал нужно завалить. Камнем. Камень я не дам.»
Данику срочно нужны рычаг и камень! Естественно, проще всего достать их у Ящера-Отшельника.
Ящер дал Данику рычаг просто так, а вот для того, чтобы получить камень, Даник должен был решить следующую задачу:
Дано целое положительное число \(n\), а также массив \(a\), содержащий целые положительные числа. Необходимо найти количество пар индексов \((i,j)\) таких, что \(i<j\) и \(a_i\) \(\&\) \(a_j \ge a_i \oplus a_j\), где \(\&\) обозначает операцию побитового И, в то время как \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Даник решил эту задачу. А сможете ли вы?
Выходные данные
Для каждого набора входных данных выведите одно целое неотрицательное число — ответ на задачу.
Примечание
В первом наборе входных данных подходит только одна пара чисел: \((4,7)\): для нее \(4\) \(\&\) \(7 = 4\), а \(4 \oplus 7 = 3\).
Во втором наборе входных данных подходит любая пара чисел.
В третьем наборе входных данных подходят две пары чисел: \((6,5)\) и \((2,3)\).
В четвертом наборе входных данных нет подходящих пар.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
1 4 3 7 10
3
1 1 1
4
6 2 5 3
2
2 4
1
1
|
1
3
2
0
0
|