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 i ≠ j) 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.
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).
The output must consist of a single line containing a single integer k indicating the number of average elements in the given sequence.
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.
We illustrate the input and output format using the above examples:
Sample Input 1:
6 3 7 10 17 22 15
Sample Output 1:
Sample Input 2:
5 3 7 10 3 18
Sample Output 2:
Sample Input 3;
5 3 8 11 17 30
Sample Output 3:
|CPU Timelimit:||3 seconds|