← 返回题目列表

Codeforces · 365/B

B. 斐波那契线段

中文机器翻译题面 查看原题

你有数组 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