You are given a sequence of integers $a_1, a_2, ..., a_N$. An element ak is said to be an average element if there are indices $i, j$ (with $i \neq  j$) such that $a_k = \frac{a_i + a_j}{2}$.
In the sequence
371022171537102217153 \quad 7 \quad 10 \quad 22 \quad 17 \quad 15
for $i=1, j=5$ and $k=3$, we get $a_k = \frac{a_i + a_j}{2}$. Thus $a_3 = 10$ is an average element in this sequence. You can check that $a_3$ is the only average element in this sequence.
Consider the sequence
371031837103183 \quad 7 \quad 10 \quad 3 \quad 18
With $i=1, j=4$ and $k=1$ we get $a_k = \frac{a_i + a_j}{2}$. Thus $a_1=3$ is an average element. We could also choose $i=1, j=4$ and $k=4$ and get $a_k = \frac{a_i + a_j}{2}$. You can check that $a_1$ and $a_4$ are the only average elements of this sequence.
On the other hand, the sequence
38111730381117303 \quad 8 \quad 11 \quad 17 \quad 30
has no average elements.
Your task is to count the number of average elements in the given sequence.

-----Input:-----
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:-----
The output must consist of a single line containing a single integer $k$ indicating the number of average elements in the given sequence.

-----Constraints:-----
- You may assume that $1 \leq N \leq 10000$.
- In $30 \%$ of the inputs $1 \leq N \leq 200$.
- In $60 \%$ of the inputs $1 \leq N \leq 5000$.

-----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

Difficulty: interview

Starter code:

Solutions:
l=[]
for _ in range(int(input())):
	l.append(int(input()))
avg=0;l.sort()
for i in range(0,len(l)):
	j=0;n=len(l)-1
	while j<n:
		s=l[j]+l[n]
		if s>2*l[i]:
			n-=1
		elif s<2*l[i]:
			j+=1
		else:
			avg+=1;break
print(avg)

def avv(l,s,n):
	i=0
	while i<n:
		ss=l[i]+l[n]
		if ss>s:
			n-=1
		elif ss<s:
			i+=1
		else:
			return True
	return False

l=[]
for _ in range(int(input())):
	l.append(int(input()))
avg=0;l.sort()
for i in range(len(l)):
		if avv(l,2*l[i],len(l)-1):
			avg+=1
print(avg)

n=int(input())
pari=[]
dispari=[]
for _ in range(n):
    appo=int(input())
    if appo%2==0:
        pari.append(appo)
    else:
        dispari.append(appo)
diz={}
for i in range(len(pari)-1):
    for j in range(i+1, len(pari)):
        diz[(pari[i]+pari[j])>>1]=1 
for i in range(len(dispari)-1):
    for j in range(i+1, len(dispari)):
        diz[(dispari[i]+dispari[j])>>1]=1 
counter=0
for el in pari:
    if el in diz:
        counter+=1
for el in dispari:
    if el in diz:
        counter+=1
print(counter)

n=int(input())
array=[]
for _ in range(n):
    array.append(int(input()))
diz={}
for i in range(n-1):
    for j in range(i+1, n):
        appo=(array[i]+array[j])
        if appo%2==0:
            diz[appo>>1]=1 
counter=0
for el in array:
    if el in diz:
        counter+=1
print(counter)

N = int(input())
numbs = []
dic = {}
e1 = set()
for i in range(N):
    numbs.append(int(input()))
    dic[numbs[i]] = 0
    e1.add(numbs[i])
for i in range(N):
    dic[numbs[i]] = dic[numbs[i]] + 1
s = set()
avg_ele = 0
for i in range(N-1):
    for j in range(i+1, N):
        avg = (numbs[i] + numbs[j])/2
        if avg in e1 and avg not in s:
            avg_ele += dic[avg]
            s.add(avg)
print(avg_ele)   

# cook your dish here
from itertools import combinations as c
try:
    n = int(input())
    dt = {}
    x = []
    for _ in range(n):
        t = int(input())
        x.append(t)
        dt[t] = dt.get(t,0) + 1
    ctr = 0
    for i in range(n-1):
        for j in range(i+1,n):
            t = x[i]+x[j]
            if t%2 == 0:
                t >>= 1
                if t in dt:
                    ctr += dt[t]
                    del dt[t]
    print(ctr)
except:
    pass

# cook your dish here
from itertools import combinations as c
try:
    n = int(input())
    x = []
    odd,even = [],[]
    for _ in range(n):
        xx = int(input())
        x.append(xx)
        if xx %2 == 0:
            even.append(xx)
        else:
            odd.append(xx)
    o = list(c(odd,2))
    e = list(c(even,2))
    #print(x,o,e)
    ctr = 0
    dt = {}
    for i in x:
        dt[i] = dt.get(i,0)+1
    tt = list(dt.values())
    ctr += sum(tt) - tt.count(1)
    for i in o:
        a,b = i
        if a != b and (a+b)//2 in x:
            ctr+=1
    for i in e:
        a,b = i
        if a!= b and (a+b)//2 in x:
            ctr+=1
    print(ctr)
except:
    pass

N = int(input())
A = sorted([int(input()) for _ in range(N)])
rets = 0
for i in range(N):
    x, y = 0,  N - 1
    curr = 2 * A[i]
    while x < y:
        sums = A[x] + A[y]
        if sums < curr: x += 1
        elif sums > curr: y -= 1
        else:
            rets += 1
            break
print(rets)



def bin_search(A, val):
    l=0;    flag=0
    r=len(arr)-1
    while l<r: 
        #print(l, r)
        if ((A[l] + A[r])== 2*val): 
            flag+=1
            break
        elif (A[l] + A[r] < 2*val): 
            l += 1
        elif(A[l]+ A[r]>2*val) :
            r -= 1
    return flag


n=int(input())
arr=[]
for i in range(n):
    x=int(input())
    arr.append(x)
    
cnt=0
arr.sort()
#print(arr)
for i in range(n):
    x=bin_search(arr, arr[i])
    if(x==1):
        cnt+=1
print(cnt)

def func(A, arr_size, val): 
      
    # sort the array 
    A.sort()
    l = 0
    r = arr_size-1
      
    # traverse the array for the two elements 
    while l<r: 
        if (A[l] + A[r] == val): 
            return 1
        elif (A[l] + A[r] < val): 
            l += 1
        else: 
            r -= 1
    return 0
    
def main():
    n=int(input())
    arr=[]
    for i in range(n):
        x=int(input())
        arr.append(x)
    cnt=0
    
    if(n==1):
        print(1)
    else:
        for i in range(n):
            #print(arr)
            x=func(arr, n, arr[i]*2)
            if(x==1):
                cnt+=1
        
        print(cnt)
    
main()

def func(A, arr_size, val): 
      
    # sort the array 
    A.sort()
    l = 0
    r = arr_size-1
      
    # traverse the array for the two elements 
    while l<r: 
        if (A[l] + A[r] == val): 
            return 1
        elif (A[l] + A[r] < val): 
            l += 1
        else: 
            r -= 1
    return 0
    
def main():
    n=int(input())
    arr=[]
    for i in range(n):
        x=int(input())
        arr.append(x)
    cnt=0
    
    for i in range(n):
        #print(arr)
        x=func(arr, n, arr[i]*2)
        if(x==1):
            cnt+=1
    
    print(cnt)
    
main()