Эвелине на Новый год подарили массив a из n неотрицательных целых чисел, каждое из которых не превосходит 2022. Её заинтересовал вопрос, сколько в этом массиве существует различных пар индексов, у которых первый индекс в паре меньше второго, таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует пар 1 <= i,j <= n, для которых выполняется ai+aj=2022.
Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.
Входные данные
В первой строке содержится одно целое число
n (1 <=
n <= 100000) - количество элементов массива. Во второй строке заданы
n целых чисел
a1,
a2,
...,
an (0 <=
ai <= 2022) - элементы массива Эвелины.
Выходные данные
Выведите одно число - количество подходящих пар.
Примечание
В первом примере не существует пар с суммой 2022.
Во втором подходят пары (1, 2), (3, 4).
В третьем примере подходят все пары (2, 4), (2, 5), (3, 4), (3, 5).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
1 2022
|
0
|
| 2 |
4
1000 1022 1001 1021
|
2
|
| 3 |
5
700 1 1 2021 2021
|
4
|