题目描述

斐波那契数列为 $1,1,2,3,5,8,\ldots$，满足 $f_i=f_{i-1}+f_{i-2}$。

定义一个长度至少为 $2$ 的序列 $A$ 为“斐波那契序列”，当且仅当 $A_i=A_{i-1}+A_{i-2}$（$i>2$）。

给出长度为 $n$ 的原序列 $B$，请从 $B$ 中选出一个子序列 $C$，使 $C$ 是斐波那契序列，并求 $C$ 的最大长度。

输入格式

本题采用文件读写。

• 读入文件名：fib.in
• 写出文件名：fib.out

第一行一个整数 $n$。

第二行 $n$ 个整数，表示序列 $B$。

输出格式

输出一个整数，表示满足条件的子序列最大长度。

样例

7
1 1 2 3 8 5 8

6

10
2 -1 0 3 -1 -1 5 8 13 -2

5

数据范围与提示

• 对于 $20\%$ 的数据，$2\le n\le100$。
• 对于另外 $10\%$ 的数据，$2\le n\le3000,-10\le B_i\le10$。
• 对于另外 $40\%$ 的数据，$2\le n\le3000,-100\le B_i\le100$。
• 对于全部数据，$2\le n\le3000,-10^9\le B_i\le10^9$。