4854: 斐波那契式
内存限制：512 MB
时间限制：3 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：7
通过：5
题目描述
D. Fibonacci-ish
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
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
- f0 and f1 are arbitrary
- fn+2=fn+1+fn for all n≥0.
Input
The first line of the input contains a single integer n (2≤n≤1000)− the length of the sequence ai. The second line contains n integers a1,a2,...,an (|ai|≤109).
Output
Print the length of the longest possible Fibonacci-ish prefix of the given sequence after rearrangement.
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。
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 ai would be Fibonacci-ish. In the second sample, the optimal way to rearrange elements is
, 
, 
, 
, 28. 输入样例 复制
输出样例 复制