Mike decided to teach programming to children in an elementary school. He knows that it is not an easy task to interest children in that age to code. That is why he decided to give each child two sweets.

Mike has $n$ sweets with sizes $a_1, a_2, \ldots, a_n$. All his sweets have different sizes. That is, there is no such pair $(i, j)$ ($1 \leq i, j \leq n$) such that $i \ne j$ and $a_i = a_j$.

Since Mike has taught for many years, he knows that if he gives two sweets with sizes $a_i$ and $a_j$ to one child and $a_k$ and $a_p$ to another, where $(a_i + a_j) \neq (a_k + a_p)$, then a child who has a smaller sum of sizes will be upset. That is, if there are two children who have different sums of sweets, then one of them will be upset. Apparently, Mike does not want somebody to be upset. 

Mike wants to invite children giving each of them two sweets. Obviously, he can't give one sweet to two or more children. His goal is to invite as many children as he can. 

Since Mike is busy preparing to his first lecture in the elementary school, he is asking you to find the maximum number of children he can invite giving each of them two sweets in such way that nobody will be upset.


-----Input-----

The first line contains one integer $n$ ($2 \leq n \leq 1\,000$) — the number of sweets Mike has.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^5$) — the sizes of the sweets. It is guaranteed that all integers are distinct.


-----Output-----

Print one integer — the maximum number of children Mike can invite giving each of them two sweets in such way that nobody will be upset.


-----Examples-----
Input
8
1 8 3 11 4 9 2 7

Output
3

Input
7
3 1 7 11 9 2 12

Output
2



-----Note-----

In the first example, Mike can give $9+2=11$ to one child, $8+3=11$ to another one, and $7+4=11$ to the third child. Therefore, Mike can invite three children. Note that it is not the only solution.

In the second example, Mike can give $3+9=12$ to one child and $1+11$ to another one. Therefore, Mike can invite two children. Note that it is not the only solution.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
sweets = [int(x) for x in input().strip().split(" ")]

dict = {}
for i in range(n - 1):
    for j in range(i + 1, n):
        sum = sweets[i] + sweets[j]
        if sum in dict:
            dict[sum] += 1
        else:
            dict[sum] = 1

print(max(dict.values()))


n=int(input())
ans=[]
l=[int(i) for i in input().split()]
for i in range(n):
    for j in range(i+1,n):
        ans.append(l[i]+l[j])
#print(ans)
from collections import Counter
c=Counter(ans)
maxi=0 
for i in c:
    if c[i]>maxi:
        maxi=c[i]
        ans=i 

print(maxi)

n = int(input())
a = sorted(list(map(int,input().split())))

from collections import defaultdict
count = defaultdict(int)
for i,x in enumerate(a[:-1]):
    for j,y in enumerate(a[i+1:]):
        count[x+y]+=1
print(max(count.values()))


f=input()

l = list(map(int, input().split()))

d = {}
ans = 0
for i in range(len(l)):
    for j in range(i+1, len(l)):
        sum = l[i] + l[j]
        if sum in d:
            d[sum] += 1
            if(d[sum] > ans): ans = d[sum]
        else:
            d[sum] = 1
            if(d[sum] > ans): ans = d[sum]
            
print(ans)

n=int(input())
arr=list(map(int,input().split()))
dict1={}
ans=0
for i in range(n):
	for j in range(i+1,n):
		try:
			dict1[arr[i]+arr[j]]+=1
		except:
			KeyError
			dict1[arr[i]+arr[j]]=1
		ans=max(ans,dict1[arr[i]+arr[j]])
print(ans)



n = int(input())
a = list(map(int, input().split()))
b = []
from collections import Counter
for i in range(n):
	for j in range(i+1,n):
		b.append(a[i]+a[j])
c = Counter(b)
x = -1
for i in c:
	x = max(x, c[i])
print(x)	

import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))

#A.sort()

B=[]
for i in range(n-1):
    for j in range(i+1,n):
        B.append(A[i]+A[j])
        
from collections import Counter
C=Counter(B)

print(max(C.values()))


n=int(input())
a=list(map(int,input().split()))

b=[0 for i in range(200005)]

if n==2: print(1)
else:
    for i in range(n-1):
        for j in range(i+1,n):
            b[a[i]+a[j]]+=1
    print(max(b))


n = int(input())
sizes = list(map(int, input().strip().split()))
count = [0 for i in range(200002)]
for i in range(n):
    for j in range(i+1,n):
        count[sizes[i] + sizes[j]] += 1
mx = 0
for i in count:
    mx = max(mx,i)
print(mx)

n = int(input())
a = list(map(int,input().split()))
cnt = [0 for i in range(2*10**5+1)]
for i in range(n):
	for j in range(i+1,n):
		cnt[a[i]+a[j]]+=1
print(max(cnt))

n = int(input())
cl = list(map(int, input().split()))

dl = [0]*(2*10**5+1)

for i in range(n):
    for j in range(i+1, n):
        d = cl[i]+cl[j]
        dl[d]+=1

mx = max(dl)

print(mx)


#n,m,k=map(int,input().split())
n=int(input())
l=list(map(int,input().split()))
d={}
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        d.setdefault(l[i]+l[j],0)
        d[l[i]+l[j]]+=1
#print(d)
print(sorted(d.values())[-1]//2)


n = int(input())
ai = list(map(int,input().split()))
num = 2 * 10 ** 5 + 1
sums = [0] * num
for i in range(n):
    for j in range(i+1,n):
        sums[ai[i] + ai[j]] += 1
print(max(sums))


def main():
    n = int(input())
    sweets = list(map(int,input().split()))
    sweets.sort()
    kids = {}

    for i in range(n):
        for j in range(i+1,n):
            s = sweets[i]+sweets[j]
            if s not in list(kids.keys()):
                kids[s] = 1
            else:
                kids[s] += 1

    max_kids = 0
    #print (kids)
    for i in list(kids.keys()):
        if kids[i] > max_kids:
            max_kids = kids[i]

    print (max_kids)

main()


n = int(input())
a = list(map(int, input().split()))
sm = []
for i in range(n):
    for j in range(i + 1, n):
        sm.append(a[i] + a[j])
        
cnt = dict()
ans = 0
for i in sm:
    if i not in cnt.keys():
        cnt[i] = 1
    else:
        cnt[i] += 1
for i in sm:
    ans = max(cnt[i], ans)
    
print(ans)

n = int(input())
a = sorted(list(map(int, input().split())))
c = [0 for i in range(n)]
d = dict()
for i in range(n):
    for j in range(n):
        if i != j:
            s = a[i] + a[j]
            if s in d:
                d[s] += 1
            else:
                d[s] = 1

ans = 0
for i in list(d.values()):
    ans = max(ans, i)
print(ans // 2)


import collections
n = int(input())
a = list(map(int, input().split()))
lis = []

for i in range(n-1):
    for j in range(i+1, n):
        lis.append(a[i] + a[j])

# print(lis)
# list.sort()
c = collections.Counter(lis)
print(c.most_common()[0][1])

n = int(input())
a = list(map(int, input().split(' ')))

sums = {}
for i in a:
    for j in a:
        if i==j:
            continue
        if i+j in sums:
            sums[i+j] += 1
        else:
            sums[i+j] = 1
print(max([sums[i] for i in list(sums.keys())])//2)


#!/usr/bin/pypy
# -*- coding: utf-8 -*-

from collections import defaultdict

def main():
    n = int(input())
    nums = list(map(int, input().split()))

    result = defaultdict(int)
    for i in range(n):
        for j in range(i + 1, n, 1):
            result[nums[i] + nums[j]] += 1
    x = max(result.values())
    print(x)





def __starting_point():
    main()

__starting_point()

from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))






n=nn()

l=lm()

d={}



for i in range(n):
	for j in range(i+1,n):
		s=l[i]+l[j]


		if s in d:
			d[s]+=1
		else:
			d[s]=1

m=0
#print(d)

for s in d:
	m=max(m,d[s])

print(m) 






def find_sum_of_two(a,n):
    #a.sort()
    d = dict()
    for i in range(n):
        for j in range(i+1,n):
            s = a[i]+a[j]
            if s in d:
                d[s] += 1
            else:
                d[s] = 1
    return max(d.values())



n = int(input()) #2-1000
a = [int(x) for x in input().split()] #x:1-10^5

print(find_sum_of_two(a,n))

n=int(input())
l=list(map(int,input().split()))
ll=[]
d={}
for i in range(n):
    for j in range(i+1,n):
        d[(l[i]+l[j])]=d.get((l[i]+l[j]),0)+1
mx=-1
for i in list(d.values()):
    if(i>mx):
        mx=i
print(mx)


n = int(input())
s = [int(x) for x in input().split()]
somas = {}
most = 0

for i in range(n-1):
    for j in range(i+1, n):
        soma = s[i]+s[j]
        if soma in somas:
            somas[soma] += 1
        else:
            somas[soma] = 1
        if somas[soma] > most:
            most = somas[soma]

print(most)

n=int(input())
a=[int(x) for x in input().split()]
d={}
for i in range(n):
    for j in range(i+1,n):
        if str(a[i]+a[j]) in d:
            d[str(a[i]+a[j])]+=1
        else:
            d[str(a[i]+a[j])]=1
m=0
for i in d:
    if(d[i]>m):
        m=d[i]
        #print(i)
print(m)

from sys import setrecursionlimit
setrecursionlimit(10**6) 
inn = lambda: input().strip()
mapp = lambda: map(int, inn().split(" "))

N = int(inn())
C = list(mapp())
C.sort()

from collections import defaultdict
summ = defaultdict(int)

for a in range(N):
    for b in range(a+1,N):
        summ[C[a]+C[b]] += 1

answer = 0
for key in summ:
    answer = max(answer, summ[key])

print(answer)