Problem 1: Average, (K Narayan Kumar, CMI)

You are given a sequence of integers a1, a2, ..., aN. An element ak is said to be an average element if there are indices i, j (with ij) such that ak = (ai + aj) / 2.

In the sequence

3  7  10  22  17  15

for i=1, j=5 and k=3, we get ak = (ai + aj)/2. Thus a3 = 10 is an average element in this sequence. You can check that a3 is the only average element in this sequence.

Consider the sequence

3  7  10  3  18

With i=1, j=4 and k=1 we get ak = (ai +aj)/2. Thus a1=3 is an average element. We could also choose i=1, j=4 and k=4 and get ak=(ai +aj)/2. You can check that a1 and a4 are the only average elements of this sequence.

On the other hand, the sequence

3  8  11  17  30

has no average elements.

Your task is to count the number of average elements in the given sequence.

Input format

The first line contains a single integer N indicating the number of elements in the sequence. This is followed by N lines containing one integer each (Line i+1 contains ai). (You may assume that ai + aj would not exceed MAXINT for any i and j).

Output format

The output must consist of a single line containing a single integer k indicating the number of average elements in the given sequence.

Test Data:

You may assume that N ≤ 10000. Further, you may assume that in 30% of the inputs N ≤ 200 and that in 60% of the inputs N ≤ 5000.

Example:

We illustrate the input and output format using the above examples:

Sample Input 1:

6
3
7
10
17
22
15

Sample Output 1:

1

Sample Input 2:

5
3
7
10
3
18

Sample Output 2:

2

Sample Input 3;

5
3
8
11
17
30

Sample Output 3:

0

CPU Timelimit: 3 seconds
Memory limit: 64M
Grading style: ioi
Register Now