Задача №114570. 2022
Эвелине на Новый год подарили массив \(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\)) — элементы массива Эвелины.
Выведите одно число — количество подходящих пар.
В первом примере не существует пар с суммой \(2022\).
Во втором примере подходят пары \((1, 2)\), \((3, 4)\).
В третьем примере подходят пары \((2, 4)\), \((2, 5)\), \((3, 4)\), (3, 5).
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(1 \leq n \leq 1500\), наберут не менее \(50\) баллов.
2 1 2022
0
4 1000 1022 1001 1021
2
5 700 1 1 2021 2021
4