No tag edit access

B. The Fibonacci Segment

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have array *a*_{1}, *a*_{2}, ..., *a*_{n}. Segment [*l*, *r*] (1 ≤ *l* ≤ *r* ≤ *n*) is good if *a*_{i} = *a*_{i - 1} + *a*_{i - 2}, for all *i* (*l* + 2 ≤ *i* ≤ *r*).

Let's define *len*([*l*, *r*]) = *r* - *l* + 1, *len*([*l*, *r*]) is the length of the segment [*l*, *r*]. Segment [*l*_{1}, *r*_{1}], is longer than segment [*l*_{2}, *r*_{2}], if *len*([*l*_{1}, *r*_{1}]) > *len*([*l*_{2}, *r*_{2}]).

Your task is to find a good segment of the maximum length in array *a*. Note that a segment of length 1 or 2 is always good.

Input

The first line contains a single integer *n* (1 ≤ *n* ≤ 10^{5}) — the number of elements in the array. The second line contains integers: *a*_{1}, *a*_{2}, ..., *a*_{n} (0 ≤ *a*_{i} ≤ 10^{9}).

Output

Print the length of the longest good segment in array *a*.

Examples

Input

10

1 2 3 5 8 13 21 34 55 89

Output

10

Input

5

1 1 1 1 1

Output

2

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/28/2017 08:32:32 (p1).

Desktop version, switch to mobile version.
User lists

Name |
---|