你有数组 a1, a2, ..., an。如果对于所有 i (l + 2 ≤ i ≤ r),ai = ai - 1 + ai - 2,则段 [l, r] (1 ≤ l ≤ r ≤ n) 是好的。
我们定义 len([l, r]) = r - l + 1,len([l, r]) 是线段 [l, r] 的长度。如果 len([l1, r1]) > len([l2, r2]),则段 [l1, r1] 比段 [l2, r2] 长。
你的任务是在数组 a 中找到最大长度的好段。请注意,长度为 1 或 2 的段总是好的。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 数组中的元素数量。第二行包含整数:a1, a2, ..., an (0 ≤ ai ≤ 109)。
输出
打印数组 a 中最长的好段的长度。
示例
输入 #1
10 1 2 3 5 8 13 21 34 55 89
输出 #1
10
输入 #2
5 1 1 1 1 1
输出 #2
2