У Монокарпа есть массив целых чисел $$$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$$$.
Название |
---|