#include<iostream>
#include <fstream>
#include<cmath>
using namespace std;
ofstream fout ("theme.out");
ifstream fin ("theme.in");
bool compar(int a1,int b1,int a2,int b2){
return (a1<a2)||(a1==a2&&b1<=b2);
}
bool compar(int a1,int b1,int c1,int a2,int b2,int c2){
return (a1<a2)||(a1==a2&&compar(b1,c1,b2,c2));
}
void radix(int n,int k,int a[],int b[],int t[]){
int c[k+1];
for(int i=0;i<=k;i++)
c[i]=0;
for(int i=0;i<n;i++)
c[t[a[i]]]++;
for(int i=0,sum=0;i<=k;i++){
int kk=c[i];
c[i]=sum;
sum+=kk;
}
for(int i=0;i<n;i++)
b[c[t[a[i]]]++]=a[i];
}
void aa(int n,int k,int sa[],int t[]){
int n1=(n+2)/3,n2=n1+n/3,n0=(n+1)/3;
int sa12[n2+3]; sa12[n2]=sa12[n2+1]=sa12[n2+2]=0;
int r[n2+3]; r[n2]=r[n2+1]=r[n2+2]=0;
int sa0[n1];
int r0[n1];
for(int i=0,j=0;i<n+n1-n0;i++)
if(i%3!=0)
r[j++]=i;
radix(n2,k,r,sa12,t+2);
radix(n2,k,sa12,r,t+1);
radix(n2,k,r,sa12,t);
int num=0,c1=-1,c2=-1,c3=-1;
for(int i=0;i<n2;i++){
if(t[sa12[i]]!=c1||t[sa12[i]+1]!=c2||t[sa12[i]+2]!=c3){
c1=t[sa12[i]];
c2=t[sa12[i]+1];
c3=t[sa12[i]+2];
num++;
}
if(sa12[i]%3==1) r[sa12[i]/3]=num;
else r[sa12[i]/3+n1]=num;
}
if(num<n2){
aa(n2,num,sa12,r);
for(int i=0;i<n2;i++)
r[sa12[i]]=i+1;
}
else
for(int i=0;i<n2;i++)
sa12[r[i]-1]=i;
for(int i=0,j=0;i<n2;i++)
if(sa12[i]<n1)
r0[j++]=sa12[i]*3;
radix(n1,k,r0,sa0,t);
for(int i=n1-n0,j=0,p=0;p<n;p++){
#define geti() (sa12[i]<n1? sa12[i]*3+1:(sa12[i]-n1)*3+2)
int ii=geti();
int jj=sa0[j];
if(sa12[i]<n1? compar(t[ii] ,r[sa12[i]+n1],t[jj] ,r[jj/3])
:compar(t[ii],t[ii+1],r[sa12[i]-n1+1],t[jj],t[jj+1],r[jj/3+n1])){
i++;
sa[p]=ii;
if(i==n2)
for(p++;j<n1;j++,p++)sa[p]=sa0[j];
}else{
sa[p]=jj;
j++;
if(j==n1)
for(p++;i<n2;i++,p++)sa[p]=geti();
}
}
}
int po(int a,int b){
int m=1;
while(b--)
m<<=1;
return m;
}
int main(){
int n;
fin>>n;
n--;
int a[n+3];
int k,k1,mi=100,ma=-100;
fin>>k;
for(int i=0;i<n;i++){
fin>>k1;
a[i]=k1-k;
k=k1;
if(a[i]<mi)
mi=a[i];
if(a[i]>ma)
ma=a[i];
}
for(int i=0;i<n;i++)
a[i]+=1-mi;
int sa[n],r[n],h[n];
for(int i=0;i<n+3;i++){
sa[i]=0;
r[i]=0;
h[i]=0;
}
a[n]=a[n+1]=a[n+2]=0;
aa(n,ma-mi+1,sa,a);
for(int i=0;i<n;i++)
r[sa[i]]=i;
ma=0;
h[0]=0;
for(int i=0;i<n;i++){
if(r[i]==0)
h[i]=0;
else
while(h[i]+i<n&&h[i]+sa[r[i]-1]<n&&a[h[i]+i]==a[h[i]+sa[r[i]-1]])
h[i]++;
h[i+1]=h[i]-1;
if(h[i+1]<0)
h[i+1]=0;
}
int l=(int)(log10(n)/log10(2)),f[n][l+1];
for(int i=0;i<n;i++)
for(int j=0;j<=l;j++)
f[i][j]=0;
for(int i=0;i<n;i++)
f[i][0]=h[sa[i]];
for(int i=1;i<l;i++)
for(int j=0;j<n;j++){
f[j][i]=f[j][i-1];
if(j+(int)(po(2,i-1))<n&&f[j+(int)(po(2,i-1))][i-1]<f[j][i])
f[j][i]=f[j+(int)(po(2,i-1))][i-1];
}
for(int i=n-1;i>=0;i--)
if(n-sa[i]>ma)
for(int j=i+1;j<n;j++)
if(n-sa[j]>ma&&(int)abs(sa[j]-sa[i])-1>ma){
int ll=min(f[i+1][(int)(log10(j-i)/log10(2))],
f[j-po(2,(int)(log10(j-i)/log10(2)))+1][(int)(log10(j-i)/log10(2))]);
int yy=min((int)abs(sa[j]-sa[i])-1,ll);
if(ma<yy)
ma=yy;
if(ll<ma) break;
}
if(ma>=4)
fout<<ma+1<<endl;
else fout<<0<<endl;
return 0;
}
评论