题面描述

兔子序列又称斐波那契序列，如果称一个长度为 $n$ 的序列 $\left\{ a_n \right\}$ 为兔子序列，当且仅当它满足下面的条件之一：

1. $n=1$ 或 $n=2$；
2. 当 $n\geqslant 3$ 时， $\forall ~ i\in [3,n]$ 满足 $a_{i-2}+a_{i-1}=a_i$。

给定一个正整数组成的数组 $a$，求数组 $a$ 的最长连续兔子子序列的长度 ^[1]。

输入描述

第一行为一个整数 $n$ 表示序列长度；其中 $n$ 满足 $1\leqslant n\leqslant 1\times 10^5$

第二行为 $n$ 个整数 $a_i$ 表示数组中每个数的个数；其中每一个数满足 $1\leqslant a_i\leqslant 1\times 10^9$。

输出描述

输出一个整数，表示 $\left\{ a_n \right\}$ 的最长连续兔子子序列的长度。

样例

8
1 1 1 1 2 3 5 1

5

5
5 2 7 9 16

5

注释

对于第一组样例 $x_1+x_2=3$ 的可能结果为：

1. $x_1=0,x_2=3$,
2. $x_1=1,x_2=2$,
3. $x_1=2,x_2=1$,
4. $x_1=3,x_2=0$.

共 4 组解。