Условие:
Алиса и Боб играют в игру с целочисленным массивом a
размера n
.
Изначально все элементы массива не имеют цвета. Сначала Алиса выбирает 3
элемента и раскрашивает их в красный цвет. Затем Боб выбирает любой элемент и раскрашивает его в синий цвет (если он был красным — перекрашивает его). Алиса выигрывает, если сумма красных элементов строго больше значения синего элемента.
Ваша задача — посчитать количество способов, которыми Алиса может выбрать 3
элемента так, чтобы она выиграла независимо от действий Боба.
Входные данные
Первая строка содержит одно целое число t
(1≤t≤1000
) — количество наборов входных данных.
В первой строке каждого набора входных данных содержится одно целое число n
(3≤n≤5000
).
Во второй строке содержатся n
целых чисел a1,a2,…,an
(1≤a1≤a2≤⋯≤an≤105
).
Дополнительное ограничение на входные данные: сумма n
по всем наборам входных данных не превышает 5000
.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество способов, которыми Алиса может выбрать 3
элемента так, чтобы она выиграла независимо от действий Боба. реши на с++