У Монокарпа есть массив целых чисел $$$a$$$, состоящий из $$$n$$$ элементов. Обозначим среднее арифметическое всех элементов массива за $$$k$$$ (обратите внимание, что $$$k$$$ может быть вещественным числом).
Среднее арифметическое массива из $$$n$$$ элементов — это сумма всех элементов массива деленная на $$$n$$$, то есть на количество элементов массива.
Монокарп решил удалить из массива $$$a$$$ ровно два элемента, при этом он хочет, чтобы после удаления среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива по-прежнему было равно $$$k$$$.
Перед вами стоит задача определить количество пар позиций $$$[i, j]$$$ ($$$i < j$$$) таких, что если удалить элементы из этих позиций, среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива будет равно $$$k$$$, то есть будет равно среднему арифметическому $$$n$$$ элементов изначального массива $$$a$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве Монокарпа.
Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно $$$i$$$-му элементу массива Монокарпа.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выведите количество пар позиций $$$[i, j]$$$ ($$$i < j$$$) таких, что если удалить элементы из этих позиций, среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива будет равно $$$k$$$, то есть будет равно среднему арифметическому $$$n$$$ элементов изначального массива $$$a$$$.
4 4 8 8 8 8 3 50 20 10 5 1 4 7 3 5 7 1 2 3 4 5 6 7
6 0 2 3
В первом примере можно удалить любую пару чисел, так как все элементы массива одинаковы.
Во второй примере нельзя удалить ни одной пары чисел таким образом, чтобы среднее арифметическое не изменилось.
В третьем примере можно удалить пару элементов в позициях $$$1$$$ и $$$3$$$ или пару элементов в позициях $$$4$$$ и $$$5$$$.
Название |
---|