Эвелине на Новый год подарили массив $$$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$$$ баллов.