B. Формирование треугольников
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ палочек, пронумерованных от $$$1$$$ до $$$n$$$. Длина $$$i$$$-й палочки равна $$$2^{a_i}$$$.

Вы хотите выбрать ровно $$$3$$$ палочки из заданных $$$n$$$ палочек и образовать из них невырожденный треугольник, используя палочки в качестве сторон треугольника. Треугольник называется невырожденным, если его площадь строго больше $$$0$$$.

Вам нужно посчитать количество способов выбрать ровно $$$3$$$ палочки, чтобы из них можно было образовать треугольник. Обратите внимание, что порядок выбора палочек не имеет значения (например, выбрать $$$1$$$-ю, $$$2$$$-ю и $$$4$$$-ю палочку — это то же самое, что и выбрать $$$2$$$-ю, $$$4$$$-ю и $$$1$$$-ю палочку).

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$);
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

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

Для каждого теста выведите одно целое число — количество способов выбрать ровно $$$3$$$ палочки, чтобы из них можно было составить треугольник.

Пример
Входные данные
4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1
Выходные данные
35
2
0
0
Примечание

В первом наборе входных данных примера можно выбрать любые три палочки из заданных $$$7$$$.

Во втором наборе входных данных примера можно выбрать $$$1$$$-ю, $$$2$$$-ю и $$$4$$$-ю палочку, или $$$1$$$-ю, $$$3$$$-ю и $$$4$$$-ю палочку.

В третьем наборе входных данных примера нельзя образовать треугольник из заданных палочек длиной $$$2$$$, $$$4$$$ и $$$8$$$.