C. Игра с раскрашиванием
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру с целочисленным массивом $$$a$$$ размера $$$n$$$.

Изначально все элементы массива не имеют цвета. Сначала Алиса выбирает $$$3$$$ элемента и раскрашивает их в красный цвет. Затем Боб выбирает любой элемент и раскрашивает его в синий цвет (если он был красным — перекрашивает его). Алиса выигрывает, если сумма красных элементов строго больше значения синего элемента.

Ваша задача — посчитать количество способов, которыми Алиса может выбрать $$$3$$$ элемента так, чтобы она выиграла независимо от действий Боба.

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

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

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$3 \le n \le 5000$$$).

Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \cdots \le a_n \le 10^5$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$.

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

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

Пример
Входные данные
6
3
1 2 3
4
1 1 2 4
5
7 7 7 7 7
5
1 1 2 2 4
6
2 3 3 4 5 5
5
1 1 1 1 3
Выходные данные
0
0
10
2
16
0
Примечание

В первых двух примерах, независимо от того, какие три элемента выберет Алиса, Боб сможет закрасить один элемент в синий цвет так, чтобы Алиса не выиграла.

В третьем примере Алиса может выбрать любые три элемента. Если Боб закрасит один из красных элементов, сумма красных элементов будет $$$14$$$, а сумма синих элементов будет $$$7$$$. Если Боб выберет незакрашенный элемент, сумма красных элементов будет $$$21$$$, а сумма синих элементов будет $$$7$$$.

В четвертом примере Алиса может выбрать либо $$$1$$$-й, $$$3$$$-й и $$$4$$$-й элементы, либо $$$2$$$-й, $$$3$$$-й и $$$4$$$-й элементы.