Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/04/2022 02:24:43 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|