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

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)


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


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))
	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:
		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()
for i in range(n):
	x = bin_search(arr, arr[i])
	if x == 1:
		cnt += 1
print(cnt)


def func(A, arr_size, val):
	A.sort()
	l = 0
	r = arr_size - 1
	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):
			x = func(arr, n, arr[i] * 2)
			if x == 1:
				cnt += 1
		print(cnt)
main()