Yash has recently learnt about the Fibonacci sequence and is very excited about it. He calls a sequence Fibonacci-ish if   the sequence consists of at least two elements  f_0 and f_1 are arbitrary  f_{n} + 2 = f_{n} + 1 + f_{n} for all n ≥ 0. 

You are given some sequence of integers a_1, a_2, ..., a_{n}. Your task is rearrange elements of this sequence in such a way that its longest possible prefix is Fibonacci-ish sequence.


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 1000) — the length of the sequence a_{i}.

The second line contains n integers a_1, a_2, ..., a_{n} (|a_{i}| ≤ 10^9).


-----Output-----

Print the length of the longest possible Fibonacci-ish prefix of the given sequence after rearrangement.


-----Examples-----
Input
3
1 2 -1

Output
3

Input
5
28 35 7 14 21

Output
4



-----Note-----

In the first sample, if we rearrange elements of the sequence as  - 1, 2, 1, the whole sequence a_{i} would be Fibonacci-ish.

In the second sample, the optimal way to rearrange elements is $7$, $14$, $21$, $35$, 28.

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3

n = int(input())
a = [int(x) for x in input().split()]

sorted_a = sorted(a)
dict_a = {}
for x in a:
    if not x in dict_a:
        dict_a[x] = 1
    else:
        dict_a[x] += 1

sorted_uniq_a = sorted(dict_a.keys())

max_fib_prefix = [a[0], a[1]]
for i in range(0, len(sorted_uniq_a)):
    for j in range(0, len(sorted_uniq_a)):
        if i != j or dict_a[sorted_uniq_a[i]] > 1:
            if sorted_uniq_a[i] + sorted_uniq_a[j] > sorted_uniq_a[-1]:
                break

            fib_prefix = [sorted_uniq_a[i], sorted_uniq_a[j]]
            dict_a[sorted_uniq_a[i]] -= 1
            dict_a[sorted_uniq_a[j]] -= 1

            while True:
                next_fib = fib_prefix[-1] + fib_prefix[-2]
                if not next_fib in dict_a or dict_a[next_fib] == 0:
                    break
                fib_prefix.append(next_fib)
                dict_a[next_fib] -= 1

            for x in fib_prefix:
                dict_a[x] += 1

            if len(fib_prefix) > len(max_fib_prefix):
                max_fib_prefix = fib_prefix

print(len(max_fib_prefix))


import sys
sys.setrecursionlimit(10000)
n = int(input())
a = list(map(int, input().split()))

# sa = dict(zip(a, range(n)))
sb = {}
for num in a:
    if not num in sb:
        sb[num]=1
    else:
        sb[num]+=1

def go(a, b):
    ans = 0
    ab = a+b
    if ab in sb and sb[ab]>0:
        sb[ab]-=1
        ans = 1 + go(b, ab)
        sb[ab]+=1
    return ans

maxans = 2
for a in sb:
    for b in sb:
        if a!=b or sb[a]>1:
            count = 2
            sb[a] -= 1
            sb[b] -= 1
            count += go(a,b)
            sb[a] += 1
            sb[b] += 1
            if count > maxans:
                maxans = count
print(maxans)

def go(a, b):
    res, c = 0, a + b
    if d.get(c) and d[c] > 0:
        d[c] -= 1
        res = go(b, c) + 1
        d[c] += 1
    return res

input()
d = {}
for i in map(int, input().split()):
    if d.get(i): d[i] += 1
    else: d[i] = 1
ans = 2
for a in d:
    for b in d:
        if a != b or d[a] > 1:
            d[a] -= 1; d[b] -= 1
            cnt = go(a, b) + 2
            d[a] += 1; d[b] += 1
            ans = max(cnt, ans)
print(ans)


n = int(input())
l = list(map(int,input().split()))
d = {}
for i in l:
	if i not in d: d[i] = 0
	d[i] += 1
ans = 0
for i in range(len(l)):
	for j in range(len(l)):
		if i==j: continue		
		n1,n2 = l[i],l[j]
		if n1==0 and n2==0: continue
		curr = 2
		d2 = {n1:1,n2:1}
		while True:
			n1,n2 = n2,n1+n2
			ans = max(ans, curr)
			if n2 in d and (d2[n2] if n2 in d2 else 0) < d[n2]:
				if n2 not in d2: d2[n2] = 0
				d2[n2] += 1
				curr += 1
			else: break
print(max(ans, (d[0] if 0 in d else -1)))


n = int(input())
a = [int(x) for x in input().split()]
D = {}
for x in a:
    if x in D:
        D[x] += 1
    else:
        D[x] = 1
maxans = 0
def check(x, y):
    num = 2
    D[x] -= 1
    D[y] -= 1
    while x+y in D and D[x+y] > 0:
        D[x+y] -= 1
        x, y = y, x+y
        num += 1
    ans = num
    while num > 2:
        D[y] += 1
        x, y = y-x, x
        num -= 1
    D[x] += 1
    D[y] += 1
    return ans

for x in D:
    for y in D:
        if x == y and D[x] == 1: continue
        maxans = max(check(x, y), maxans)

print(maxans)



n = int(input())
a = [int(x) for x in input().split()]
n0 = len([x for x in a if x == 0])
a = [x for x in a if x != 0]
if n0 > 0:
    a.append(0)
n = len(a)
#print("a: ", a)

pos = {}
for i in range(n):
    if a[i] in pos:
        pos[a[i]] += 1
    else:
        pos[a[i]] = 1

res = []
max_r = n0

if max_r < 2:
    max_r = 2
pr = {}
for i in range(0, n):
    for j in range(0, n):
        if i == j:
            continue
        """ 
        if (a[j], a[i]+a[j]) in pr:
            res = pr[(a[j], a[i]+a[j])] + 1
            pr[(a[i], a[j])] = res
            if res > max_r:
                max_r = res
            continue
        """
        if (a[i], a[j]) in pr:
            continue
        if a[i]+a[j] not in pos:
            continue
        res = 2
        a1 = a[i]
        a2 = a[j]
        s = a1 + a2
        m = []
        pos[a1] -= 1
        pos[a2] -= 1
        m.append(a1)
        m.append(a2)
        while (s in pos) and (pos[s] > 0):
            pos[s] -= 1
            m.append(s)
            res += 1
            a1 = a2
            a2 = s
            s = a1 + a2

        for k in range(len(m)):
            pos[m[k]] += 1
            if k > 0:
                pr[(m[k-1], m[k])] = res - k + 1
        if res > max_r:
            max_r = res
        pr[(a[i], a[j])] = res

print(max_r)


def main():
    from collections import Counter
    n = int(input())
    cnt, res = dict(Counter(list(map(int, input().split())))), []
    if cnt.get(0, 0) * 2 >= n:
        print(cnt[0])
        return
    cget, rpush = cnt.get, res.append

    def deeper(a, b, lvl):
        if cget(a + b, 0):
            c = a + b
            cnt[c] -= 1
            deeper(b, c, lvl + 1)
            cnt[c] += 1
        else:
            rpush(lvl)

    for x in cnt:
        cnt[x] -= 1
        for y in cnt:
            if cnt[y]:
                cnt[y] -= 1
                deeper(x, y, 2)
                cnt[y] += 1
        cnt[x] += 1
    print(max(res))


def __starting_point():
    main()

__starting_point()

def main():
    from collections import Counter
    n = int(input())
    cnt, res = dict(Counter(list(map(int, input().split())))), []
    x = cnt.get(0, 0)
    if x * 2 >= n:
        print(cnt[0])
        return
    cget, rpush = cnt.get, res.append
    if x:
        rpush(x)
        cnt[0] = 1

    def deeper(a, b, lvl):
        if cget(a + b, 0):
            c = a + b
            cnt[c] -= 1
            deeper(b, c, lvl + 1)
            cnt[c] += 1
        else:
            rpush(lvl)

    for x in cnt:
        cnt[x] -= 1
        for y in cnt:
            if cnt[y]:
                cnt[y] -= 1
                deeper(x, y, 2)
                cnt[y] += 1
        cnt[x] += 1
    print(max(res))


def __starting_point():
    main()

__starting_point()

def go(a,b):
    ret,c=0,a+b
    if d.get(c) and d[c]>0:
        d[c]-=1
        ret=go(b,c)+1
        d[c]+=1
    return ret

input()
d={}
for i in map(int,input().split()):
    if d.get(i):d[i]+=1
    else: d[i]=1

ans=2
for a in d:
    for b in d:
        if a!=b or d[a]>1:
            d[a]-=1
            d[b]-=1
            temp=go(a,b)+2
            ans=max(temp,ans)
            d[a]+=1
            d[b]+=1
print(ans)


from collections import Counter


def go(a, b, counter):
    res, c = 0, a + b
    if counter.get(c) and counter[c] > 0:
        counter[c] -= 1
        res = max(res, go(b, c, counter) + 1)
        counter[c] += 1
    return res


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    counter = Counter(a)
    res = 2
    for a in counter:
        for b in counter:
            if (a != 0 or b != 0) and (a != b or counter[a] > 1):
                counter[a] -= 1
                counter[b] -= 1
                res = max(res, go(a, b, counter) + 2)
                counter[a] += 1
                counter[b] += 1
    res = max(res, counter[0])
    print(res)

main()

'''
Created on Aug 26, 2016

@author: Md. Rezwanul Haque
'''
'''
F = []
a,b = 0,1
#F.append(a)
for _ in range(5):
    F.append(b)
    a,b = b,a+b
print(F)
'''
def go(a,b):
    res, c = 0,a+b
    if d.get(c) and d[c]>0:
        d[c] -= 1
        res = go(b,c) + 1
        d[c] += 1
        #print("Res : " ,res)
    return res 
input()
d = {}
for i in map(int, input().split()):
    if d.get(i):
        d[i] += 1
    else:
        d[i] = 1
ans = 2
for a in d:
    for b in  d:
        if a != b or d[a] >1 :
            d[a] -= 1
            d[b] -= 1
            cnt  = go(a,b) + 2
            d[a] += 1
            d[b] += 1
            ans =  max(ans, cnt)
print(ans) 

def rec(a, b):
    res, c = 0, a + b
    if d.get(c) and d[c] > 0:
        d[c] -= 1
        res = rec(b, c) + 1
        d[c] += 1
    return res

input()
d = {}
for i in map(int, input().split()):
    if d.get(i):
        d[i] += 1
    else:
        d[i] = 1
ans = 2
for a in d:
    for b in d:
        if a != b or d[a] > 1:
            d[a] -= 1
            d[b] -= 1
            cnt = rec(a, b) + 2
            d[a] += 1
            d[b] += 1
            ans = max(ans, cnt)
print(ans)


n = int(input())
a = [int(i) for i in input().split()]
ans = a.count(0)
d, s = dict(), set(a)
for i in a:
    if i not in list(d.keys()):
        d[i] = 0
    d[i] += 1
for i in range(n):
    for j in range(n):
        if i == j or a[i] == a[j] == 0: continue
        a1, a2 = a[i], a[j]
        ln, dl = 2, [a1, a2]
        d[a1] -= 1
        d[a2] -= 1
        while a1 + a2 in s:
            a1, a2 = a2, a1 + a2
            d[a2] -= 1
            dl.append(a2)
            if d[a2] < 0:
                break
            ln += 1
        ans = max(ans, ln)
        for v in dl:
            d[v] += 1
print(ans)


from collections import Counter
input()
s = Counter(map(int, input().split()))
n = 0
for q in s:
    s[q] -= 1
    for a in s:
        if not s[a]: continue
        t = [a]
        s[a] -= 1
        b = q + a
        while s.get(b, 0):
            s[b] -= 1
            t.append(b)
            a, b = b, a + b
        n = max(n, len(t))
        for c in t: s[c] += 1
    s[q] += 1
print(n + 1)

n = int(input())
a = list(map(int,input().split()))
ans = a.count(0)
d = {}
for i in a:
	if i not in d:
		d[i] = 1
	else:
		d[i] += 1

ans = max(ans, 2)

for i in range(n):
	for j in range(n):
		
		if(i != j and (a[i] != 0 or a[j] != 0)):

			first = a[i]
			second = a[j]
			temp = [first, second]
			third = first + second

			while(True):

				if abs(third) > int(1e9):
					break

				if third not in d:
					break

				temp.append(third)

				first = second
				second = third
				third = first + second

			count = 0
			f = 1
			for k in range(len(temp)):
				if d[temp[k]] > 0:
					d[temp[k]] -= 1
					count += 1
				else:
					f = 0
					for j in range(k):
						d[temp[j]] += 1
					break
			if f:
				for k in temp:
					d[k] += 1
			ans = max(ans, count)


print(ans)


from collections import Counter

n = int(input())
s = Counter(list(map(int, input().split())))
n = 0

for q in s:
    s[q] -= 1

    for a in s:
        if s[a]:
            t = [a]
            s[a] -= 1
            b = q + a

            while s.get(b, 0):
                s[b] -= 1
                t.append(b)
                a, b = b, a + b

            n = max(n, len(t))

            for c in t:
                s[c] += 1
    s[q] += 1

print(n + 1)


from collections import Counter

n = int(input())
s = Counter(list(map(int, input().split())))
n = 0

for q in s:
    s[q] -= 1

    for a in s:
        if s[a]:
            t = [a]
            s[a] -= 1
            b = q + a

            while s.get(b, 0):
                s[b] -= 1
                t.append(b)
                a, b = b, a + b

            n = max(n, len(t))

            for c in t:
                s[c] += 1
    s[q] += 1

print(n + 1)


import random, math
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right
from collections import Counter


# Function to call the actual solution
def solution(li):
	ma = {}
	for i in range(len(li)):
		ma[li[i]] = ma.get(li[i], 0) + 1
	# ma1 = dc(ma)
	ans = 0
	# li = list(set(li))
	for i in range(len(li)):
		for j in range(len(li)):
			if i != j:
				f0 = li[i]
				f1 = li[j]
				if f0 == 0 and f1 == 0:
					ans = max(ans, ma[0])
					continue

				ma[f0] -= 1
				ma[f1] -= 1
				cur = 2
				while True:
					nxt = f0 + f1
					if nxt in ma and ma[nxt] > 0:
						f0 = f1 + 1 - 1
						f1 = nxt + 1 - 1
						ma[nxt] -= 1
						cur += 1
					else:
						break
				cur1 = 2
				ma[f0] += 1
				ma[f1] += 1
				while cur1 < cur:
					prev = f1 - f0
					f1 = f0 + 1 - 1
					f0 = prev + 1 - 1
					ma[prev] += 1
					cur1 += 1
				ans = max(ans, cur)
	return ans


# Function to take input
def input_test():
		n = int(input())
		li = list(map(int, input().strip().split(" ")))
		out = solution(li)
		print(out)

# Function to test my code
def test():
	pass


input_test()
# test()


from copy import * 
length=int(input())
arr=list(map(int,input().split()))
d=dict()
for i in arr:
    d[i]=d.get(i,0)+1
ans=0
for i in range(len(arr)):
    for j in range(len(arr)):
        if i!=j:
            if arr[i]==0 and arr[j]==0:
                ans=max(ans,d[arr[i]])
            else:
                count=2
                a=arr[i]
                b=arr[j]
                d[a]-=1 
                d[b]-=1 
                for k in range(100):
                    if d.get(a+b):
                        count+=1 
                        d[a+b]-=1 
                        c=a+b
                        a=b
                        b=c
                    else:
                        d[a]+=1 
                        d[b]+=1
                        ans=max(ans,count)
                        break
                y=count-2 
                while y>0:
                    c=b-a 
                    d[c]=d.get(c,0)+1 
                    b=a 
                    a=c 
                    y-=1 
print(ans)


from copy import * 
length=int(input())
arr=list(map(int,input().split()))
d=dict()
for i in arr:
    d[i]=d.get(i,0)+1
ans=0
for i in range(len(arr)):
    for j in range(len(arr)):
        if i!=j:
            if arr[i]==0 and arr[j]==0:
                ans=max(ans,d[arr[i]])
            else:
                count=2
                a=arr[i]
                b=arr[j]
                d[a]-=1 
                d[b]-=1 
                for k in range(100):
                    if d.get(a+b):
                        count+=1 
                        d[a+b]-=1 
                        c=a+b
                        a=b
                        b=c
                    else:
                        d[a]+=1 
                        d[b]+=1
                        ans=max(ans,count)
                        break
                y=count-2 
                while y>0:
                    c=b-a 
                    d[c]=d.get(c,0)+1 
                    b=a 
                    a=c 
                    y-=1 
print(ans)


from sys import stdin, stdout

def fin(): return stdin.readline().strip()
def fout(x): stdout.write(str(x) + '\n')

def m_add(mp, val):
    mp[val] = mp.get(val, 0) + 1
def m_remove(mp, val):
    if mp[val] == 1:
        mp.pop(val)
    else:
        mp[val] -= 1


n, arr, mp, res = int(fin()), list(map(int, fin().split())), {}, 0
for i in arr: m_add(mp, i)

for i in range(n):
    for j in range(n):
        if i == j: continue
        cnt, a, b = 2, arr[i], arr[j]

        if a == 0 and b == 0:
            res = max(res, mp[0])
            continue

        m_remove(mp, a)
        m_remove(mp, b)
        
        while a+b in mp:
            m_remove(mp, a+b)
            a, b = b, a+b
            cnt += 1
        
        res = max(res, cnt)
        while a != arr[i] or b != arr[j]:
            a, b = b - a, a
            m_add(mp, a+b)
        
        m_add(mp, a)
        m_add(mp, b)
print(res)