开始 2019-05-31 18:30:00

517编程-IOI赛制测试赛

结束 2019-06-01 18:30:00
Contest is over.
当前 2020-05-30 03:16:25

G. 菲波那切数列挑战

描述

一个序列如果被称为斐波那契序列,说明这个序列除了前两个元素的其他元素都等于他之前两个元素的和,特殊的,只有0个,1个或者2个元素的序列都为斐波那契序列

比如$ (1, 1, 2, 3, 5, 8) (4, 2, 6, 8, 14, 22)$都是斐波那契序列
 

现在有一个整数的集合S

1:517从中挑选若干个数(可能是0个)组合成一个斐波那契序列的子序列

2:518对剩下的数进行同样的操作

3:最后将517与518挑选出来的序列进行拼接,518的序列接在517序列的后面,拼接后的序列必须是有序的,并且他们希望元素个数越多越好
 

输出拼接序列中最多可能的元素个数

输入

第一行输入一个整数$n$ ($1 \le n \le 50$)

第二行输入$n$个整数表示S集合

数据范围为 $[1-10^8]$,S集合每个数都是不同的
 

输出

输出一个整数

样例

输入

5
8 1 20 3 10

输出

5

输入

6
19 47 50 58 77 99

输出

4

输入

8
3 5 7 10 13 15 20 90

输出

7

提示

样例一解释:

517选择了1 3 8,是 1 1 2 3 5 8 13的子序列

518选择了10 20
 

样例3解释

517选择了3 5 7 是 3 2 5 7的子序列

518选择了10 15 20 90 是10 5 15 20 35 55 90的子序列
 

子任务1: n <= 10

子任务2: n <= 20

子任务3: 无限制

时间限制 1 秒
内存限制 128 MB