У вас есть \(n\) палочек, пронумерованных от \(1\) до \(n\). Длина \(i\)-й палочки равна \(2^{a_i}\).
Вы хотите выбрать ровно \(3\) палочки из заданных \(n\) палочек и образовать из них невырожденный треугольник, используя палочки в качестве сторон треугольника. Треугольник называется невырожденным, если его площадь строго больше \(0\).
Вам нужно посчитать количество способов выбрать ровно \(3\) палочки, чтобы из них можно было образовать треугольник. Обратите внимание, что порядок выбора палочек не имеет значения (например, выбрать \(1\)-ю, \(2\)-ю и \(4\)-ю палочку — это то же самое, что и выбрать \(2\)-ю, \(4\)-ю и \(1\)-ю палочку).
Выходные данные
Для каждого теста выведите одно целое число — количество способов выбрать ровно \(3\) палочки, чтобы из них можно было составить треугольник.
Примечание
В первом наборе входных данных примера можно выбрать любые три палочки из заданных \(7\).
Во втором наборе входных данных примера можно выбрать \(1\)-ю, \(2\)-ю и \(4\)-ю палочку, или \(1\)-ю, \(3\)-ю и \(4\)-ю палочку.
В третьем наборе входных данных примера нельзя образовать треугольник из заданных палочек длиной \(2\), \(4\) и \(8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1
|
35
2
0
0
|