记录编号	470522	评测结果	AAAAAAAAAAAAAAA
题目名称	乐曲主题	最终得分	100
用户昵称	Continue	是否通过	通过
代码语言	C++	运行时间	0.779 s
提交时间	2017-11-04 20:44:10	内存使用	0.41 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

typedef unsigned long long ull;
const int base=199;
const int maxn=5000+5;

ull power[maxn],hash[maxn];

void init(int n) {
	power[0]=1;
	for(int i=1;i<=n;i++) power[i]=power[i-1]*base;
}

ull Hash(int l,int r) {
	return hash[r]-hash[l-1]*power[r-l+1];
}

int note[maxn],n;

bool check(int l) {
	for(int i=1;i<=n-l+1;i++) {
		ull h=Hash(i,i+l-2);
		for(int j=i+l;j<=n-l+1;j++)
			if(Hash(j,j+l-2)==h) return true;
	}
	return false;
}

int bearch(int l,int r) {
	for(int i=1;i<n;i++) {
		note[i]=note[i+1]-note[i]+87;
		hash[i]=hash[i-1]*base+note[i];
	}
	
	int ret=0;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1,ret=mid;
		else r=mid-1;
	}
	return ret;
}

int main() {
	freopen("theme.in","r",stdin);
	freopen("theme.out","w",stdout);
	
	scanf("%d",&n);
	init(n);
	for(int i=1;i<=n;i++)
		scanf("%d",&note[i]);
	int ans=bearch(5,n);
	printf("%d\n",ans);
	return 0;
}