E. Удаление двух элементов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть массив целых чисел $$$a$$$, состоящий из $$$n$$$ элементов. Обозначим среднее арифметическое всех элементов массива за $$$k$$$ (обратите внимание, что $$$k$$$ может быть вещественным числом).

Среднее арифметическое массива из $$$n$$$ элементов — это сумма всех элементов массива деленная на $$$n$$$, то есть на количество элементов массива.

Монокарп решил удалить из массива $$$a$$$ ровно два элемента, при этом он хочет, чтобы после удаления среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива по-прежнему было равно $$$k$$$.

Перед вами стоит задача определить количество пар позиций $$$[i, j]$$$ ($$$i < j$$$) таких, что если удалить элементы из этих позиций, среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива будет равно $$$k$$$, то есть будет равно среднему арифметическому $$$n$$$ элементов изначального массива $$$a$$$.

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

В первой строке следует целое число $$$n$$$ ($$$3 \le n \le 200\,000$$$) — количество элементов в массиве Монокарпа.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно $$$i$$$-му элементу массива Монокарпа.

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

Выведите количество пар позиций $$$[i, j]$$$ ($$$i < j$$$) таких, что если удалить элементы из этих позиций, среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива будет равно $$$k$$$, то есть будет равно среднему арифметическому $$$n$$$ элементов изначального массива $$$a$$$.

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

В первом примере можно удалить любую пару чисел, так как все элементы массива одинаковы.

Во второй примере нельзя удалить ни одной пары чисел таким образом, чтобы среднее арифметическое не изменилось.

В третьем примере можно удалить пару элементов в позициях $$$1$$$ и $$$3$$$ или пару элементов в позициях $$$4$$$ и $$$5$$$.