Fibonacci-ish

题意翻译

Yash最近迷上了fibonacci数列，他定义了一种数列叫fibonacccccci数列： 1． 这个数列包含至少2个元素； 2． f[0]和f[1]是任意选取的； 3． f[n+2]=f[n+1]+f[n] (n>=0)； 现在，给出一个数列a[1..n]，你可以改变数列元素的顺序，使得a[1..m] 满足fibonacccccci数列的条件，请求出最大的m。 【输入数据】 第一行1个数n，表示数列长度

题目描述

Yash has recently learnt about the Fibonacci sequence and is very excited about it. He calls a sequence Fibonacci-ish if 1. the sequence consists of at least two elements 2. $ f_{0} $ and $ f_{1} $ are arbitrary 3. $ 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.

输入输出格式

输入格式

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} $ ).

输出格式

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

输入输出样例

输入样例 #1

3
1 2 -1

输出样例 #1

3

输入样例 #2

5
28 35 7 14 21

输出样例 #2

4

说明

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 , , , , $ 28 $ .