记录编号	122380	评测结果	AAAAAAAAAAAAAAA
题目名称	乐曲主题	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2014-09-23 13:25:31	内存使用	1.00 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=20010,INF=0x7fffffff/2;
int sum[SIZEN]={0};//桶排序用的数组
void basesort(int a[],int b[],int c[],int n,int m){//排序前a,排序后b,关键字c,下标1~n,关键字范围0~m
	for(int i=0;i<=m;i++) sum[i]=0;
	for(int i=1;i<=n;i++) sum[c[a[i]]]++;
	for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
	for(int i=n;i>=1;i--) b[sum[c[a[i]]]--]=a[i];
}
int A[SIZEN]={0},B[SIZEN]={0};//两个临时数组
int x[SIZEN]={0},y[SIZEN]={0};//临时存放第一和第二关键字
void sort_suf(int S[],int rank[],int sa[],int N){//串S,名次数组rank,顺序数组sa,下标1~N
	//第一次排序比较特殊,直接对S中的元素拍
	for(int i=1;i<=N;i++) x[i]=S[i],A[i]=i;
	basesort(A,sa,x,N,256);
	//计算出rank数组,这将是以后比较用的关键字
	rank[sa[1]]=1;
	for(int i=2;i<=N;i++)
		if(x[sa[i-1]]==x[sa[i]]) rank[sa[i]]=rank[sa[i-1]];
		else rank[sa[i]]=rank[sa[i-1]]+1;
	for(int k=1;k<=N;k<<=1){
		for(int i=1;i<=N;i++){
			x[i]=rank[i];
			y[i]=i+k<=N?rank[i+k]:0;
			A[i]=i;
		}
		basesort(A,B,y,N,N);
		basesort(B,sa,x,N,N);
		rank[sa[1]]=1;
		for(int i=2;i<=N;i++)
			if(x[sa[i-1]]==x[sa[i]]&&y[sa[i-1]]==y[sa[i]]) rank[sa[i]]=rank[sa[i-1]];
			else rank[sa[i]]=rank[sa[i-1]]+1;
	}
	for(int i=1;i<=N;i++) rank[sa[i]]=i;//最后计算出rank的真正值
}
//height[i]:suf[sa[i-1]]与suf[sa[i]]的LCP,即排名为i和排名i-1的两个后缀的LCP
void calc_height(int S[],int rank[],int sa[],int height[],int N){
	int h=0;//后缀i和它前面那个后缀的height
	for(int i=1;i<=N;i++){
		if(rank[i]==1) h=0;
		else{
			int k=sa[rank[i]-1];
			if(--h<0) h=0;//h-1
			while(S[i+h]==S[k+h]) h++;
		}
		height[rank[i]]=h;
	}
}
int N;
int S[SIZEN]={0};
int rank[SIZEN]={0},sa[SIZEN]={0},height[SIZEN]={0};
bool test(int k){//长度>=k的?
	int i=1,j;
	while(i<N){
		int j=i+1,mx,mn;
		mx=mn=sa[i];
		while(j<=N&&height[j]>=k){
			mx=max(mx,sa[j]);
			mn=min(mn,sa[j]);
			j++;
		}
		if(mx-mn>k) return true;
		i=j;
	}
	return false;
}
void work(void){
	int l=1,r=N/2;
	while(l<r){
		int mid=(l+r)/2;
		if(test(mid+1)) l=mid+1;
		else r=mid;
	}
	if(l>=4) printf("%d\n",l+1);
	else printf("0\n");
}
void prepare(void){
	sort_suf(S,rank,sa,N);
	calc_height(S,rank,sa,height,N);
}
bool read(void){
	scanf("%d",&N);
	if(!N) return false;
	memset(S,0,sizeof(S));
	for(int i=1;i<=N;i++) scanf("%d",&S[i]);
	for(int i=1;i<=N-1;i++) S[i]=S[i+1]-S[i]+90;
	N--;
	return true;
}
int main(){
	freopen("theme.in","r",stdin);
	freopen("theme.out","w",stdout);
	read();
	prepare();
	work();
	/*while(read()){
		prepare();
		work();
	}*/
	return 0;
}