2022
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эвелине на Новый год подарили массив $$$a$$$ из $$$n$$$ неотрицательных целых чисел, каждое из которых не превосходит $$$2022$$$. Её заинтересовал вопрос, сколько в этом массиве существует различных пар индексов, у которых первый индекс в паре меньше второго, таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует пар $$$ 1\leq i < j \leq n$$$, для которых выполняется $$$a_i + a_j = 2022$$$.

Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.

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

В первой строке содержится одно целое число $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — количество элементов массива.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2022$$$) — элементы массива Эвелины.

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

Выведите одно число — количество подходящих пар.

Примеры

Входные данные
2
1 2022
Выходные данные
0
Входные данные
4
1000 1022 1001 1021
Выходные данные
2
Входные данные
5
700 1 1 2021 2021
Выходные данные
4

Примечание

В первом примере не существует пар с суммой $$$2022$$$.

Во втором примере подходят пары $$$(1, 2)$$$, $$$(3, 4)$$$.

В третьем примере подходят пары $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(3, 4)$$$, (3, 5).

Система оценки

В данной задаче $$$50$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$2$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$1 \leq n \leq 1500$$$, наберут не менее $$$50$$$ баллов.