Eveline was presented with an array a of n non-negative integers, each of which does not exceed 2022. She was interested in the question of how many different pairs of indices exist in this array, whose first index in the pair is less than the second, such that the sum of the corresponding elements of the array is 2022. Formally, she wants to understand how many pairs there are 1 <= i,j <= n for which ai +aj=2022.
February has already arrived, and Evelina still hasn't had time to calculate the answer to the question, because the array is too large. But she was able to remember it and told you about her array to get help finding the answer.
Input
The first line contains a single integer
n (1 <=
n <= 100000) - the number of array elements. The second line contains
n integers
a1,
a2,
...,
an (0 <=
ai <= 2022) - elements of Evelina's array.
Imprint
Print one number - the number of matching pairs.
Note
In the first example, there are no fours with the sum of 2022.
Pairs (1, 2), (3, 4) fit in the second one.
In the third example, all pairs (2, 4), (2, 5), (3, 4), (3, 5) match.
Examples
| # |
Input |
Output |
| 1 |
2
1 2022
|
0
|
| 2 |
4
1000 1022 1001 1021
|
2
|
| 3 |
5
700 1 1 2021 2021
|
4
|