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.

Source: codeforces | Difficulty: HARD
Tags: String algorithms

Implementation

Complete search

Dynamic programming

Mathematics


Solutions:
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)


def main():
	from collections import Counter
	n = int(input())
	(cnt, res) = (dict(Counter(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))
main()


import sys, collections
sys.setrecursionlimit(10000)
d = collections.defaultdict(int)

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()
for i in map(int, input().split()):
	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)


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

def solution(li):
	ma = {}
	for i in range(len(li)):
		ma[li[i]] = ma.get(li[i], 0) + 1
	ans = 0
	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

def input_test():
	n = int(input())
	li = list(map(int, input().strip().split(' ')))
	out = solution(li)
	print(out)

def test():
	pass
input_test()


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


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)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
l = list(map(int, input().split()))
cou = {}
for i in l:
	if i in cou:
		cou[i] += 1
	else:
		cou[i] = 1

def find(x, y):
	num = 2
	cou[x] -= 1
	cou[y] -= 1
	while x + y in cou and cou[x + y] > 0:
		cou[x + y] -= 1
		(x, y) = (y, x + y)
		num += 1
	ans = num
	while num > 2:
		cou[y] += 1
		(x, y) = (y - x, x)
		num -= 1
	cou[x] += 1
	cou[y] += 1
	return ans
ans = 2
for x in cou:
	for y in cou:
		if x == y and cou[x] == 1:
			continue
		ans = max(find(x, y), ans)
print(ans)


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)


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)


import sys
sys.setrecursionlimit(10000)
n = int(input())
a = list(map(int, input().split()))
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)


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(1000000000.0):
					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)


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)


n = int(input())
a = list(map(int, input().split()))
s = {}
d = {}
p = set()
mx = -10 ** 15
mi = -mx
ans = 2
for i in range(n):
	if a[i] in s:
		s[a[i]] += 1
	else:
		s[a[i]] = 1
	mx = max(mx, a[i])
	mi = min(mi, a[i])
if 0 in s:
	ans = max(ans, s[0])
for i in range(n):
	for j in range(n):
		if j == i or (a[i] == 0 and a[j] == 0) or (a[i], a[j]) in p:
			continue
		f0 = a[i]
		f1 = a[j]
		ansi = 2
		f2 = 0
		d = {}
		p.add((a[i], a[j]))
		while True:
			f2 = f1 + f0
			f0 = f1
			f1 = f2
			if f2 > mx or f2 < mi:
				break
			if f2 in s:
				d[f2] = s[f2]
			else:
				break
		f0 = a[i]
		f1 = a[j]
		if f1 == f0:
			d[f0] = s[f0] - 2
		else:
			d[f0] = s[f0] - 1
			d[f1] = s[f1] - 1
		while True:
			f2 = f1 + f0
			f0 = f1
			f1 = f2
			if f2 > mx or f2 < mi:
				break
			if f2 in d and d[f2] > 0:
				ansi += 1
				d[f2] -= 1
			else:
				break
		ans = max(ans, ansi)
print(ans)


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


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


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)


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