The Fibonacci Segment

 

You have array a₁, a₂, ..., 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₁, r₁], is longer than segment [l₂, r₂], if len([l₁, r₁]) > len([l₂, r₂]).

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⁵) — the number of elements in the array. The second line contains integers: a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹).

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 sol：找最长的满足斐波那契数列性质的数列，容易发现只要55个数字就会数字大小就会爆int，但是如果你直接暴力的话100000个0你就T飞了 所以把一串0缩成一个点，在暴力 但是有一堆地方要特判，我跪的很惨（我太菜菜菜菜菜菜菜菜菜菜了）

#include 
        
         using namespace std;typedef int ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-'); ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-'); x=-x;    }    if(x<10)    {        putchar(x+'0'); return;    }    write(x/10);    putchar((x%10)+'0');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')const int N=100005;int n;int a[N],A[N],Len[N];int main(){    int i,j,ans=1;    R(n);    if(n<=2) {Wl(n); return 0;}    for(i=1;i<=n;i++)    {        R(a[i]);    }    *A=0;    for(i=1;i<=n;i++)    {        if(a[i]>0)        {            A[++*A]=a[i];            Len[*A]=1;        }        else        {            A[++*A]=0;            for(;i<=n&&a[i]==0;i++) Len[*A]++;            i--;        }    }    for(i=1;i<=n;i++) ans=max(ans,Len[i]);    if(*A==1) ans=n;    if(*A==2)    {        if(A[1]==0) ans=max(Len[1],Len[2]+1);        else ans=Len[2];    }    for(i=1;i<=(*A)-2;i++)    {        int tmp;        if(A[i]==0)        {            tmp=Len[i+1]+1;        }        else if(A[i+1]==0)        {            if(Len[i+1]==1) tmp=Len[i+1]+1;            else            {                tmp=1+Len[i+2];                for(j=i+3;j<=*A;j++)                {                    if(A[j]==A[j-1]+A[j-2]) tmp+=Len[j];                    else break;                }                ans=max(ans,tmp);                continue;            }        }        else tmp=Len[i]+Len[i+1];        for(j=i+2;j<=*A;j++)        {            if(A[j]==A[j-1]+A[j-2]) tmp+=Len[j];            else break;        }        ans=max(ans,tmp);    }    Wl(ans);    return 0;}/*input101 2 3 5 8 13 21 34 55 89output10input51 1 1 1 1output2input101 1 0 0 0 0 0 0 0 1output7*/