• HOME
• ACTIVITIES
• OLYMPIAD
• MEMBERS
• ABOUT

Related:

• Overview
• Current
• Study Material
• Online Judge
• Archives

Indian National Olympiad in Informatics

Online Programming Contest, 1-2 January 2005

IARCS home > OLYMPIAD

Advanced Division

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

You are given a sequence of integers a₁, a₂, ..., a_N. An element a_k is said to be an average element if there are indices i, j (with i ≠ j) such that a_k = (a_i + a_j) / 2.

In the sequence

3  7  10  22  17  15

for i=1, j=5 and k=3, we get a_k = (a_i + a_j)/2. Thus a₃ = 10 is an average element in this sequence. You can check that a₃ 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 a_k = (a_i +a_j)/2. Thus a₁=3 is an average element. We could also choose i=1, j=4 and k=4 and get a_k=(a_i +a_j)/2. You can check that a₁ and a₄ 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 a_i). (You may assume that a_i + a_j 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