记录编号	283763	评测结果	AAAAAAAAAAAAAAA
题目名称	乐曲主题	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2016-07-15 12:51:40	内存使用	0.39 MiB

//KZNS
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Nmax = 5003;
int N;
int A[Nmax];

int sa[Nmax], rank[Nmax], height[Nmax];
int *x = rank, *y = height, *uu;
int buk[Nmax];
int tps;
int p;
void get_sa() {
	memset(buk, 0, sizeof(buk));
	for (int i = 0; i < N; i++) buk[x[i] = A[i]]++;
	for (int i = 1; i < tps; i++) buk[i] += buk[i-1];
	for (int i = N-1; i >= 0; i--)
		sa[--buk[x[i]]] = i;
	
	for (int k = 1; k < N; k<<=1) {
		p = 0;
		for (int i = N-k; i < N; i++) y[p++] = i;
		for (int i = 0; i < N; i++) if (sa[i] >= k) y[p++] = sa[i]-k;
		
		memset(buk, 0, sizeof(int)*tps);
		for (int i = 0; i < N; i++) buk[x[i]]++;
		for (int i = 1; i < tps; i++) buk[i] += buk[i-1];
		for (int i = N-1; i >= 0; i--) sa[--buk[x[y[i]]]] = y[i];
		
		uu = x; x = y; y = uu;
		x[sa[0]] = 1;
		p = 1;
		for (int i = 1; i < N; i++)
			x[sa[i]] = (y[sa[i]]==y[sa[i-1]]&&(sa[i]+k<N?y[sa[i]+k]:0)==(sa[i-1]+k<N?y[sa[i-1]+k]:0) ? p : ++p);
		if (p == N)
			break;
		else
			tps = p+1;
	}
}
void get_rank() {
	for (int i = 0; i < N; i++)
		rank[sa[i]] = i;
}
void get_height() {
	int h = 0, k;
	for (int i = 0; i < N; i++) {
		if (rank[i]) {
			k = sa[rank[i]-1];
			if (h)
				h--;
			while (A[i+h] == A[k+h]) h++;
		}
		else {
			h = 0;
		}
		height[rank[i]] = h;
	}
}
void rin() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", A+i);
	}
	for (int i = N-1; i > 0; i--)
		A[i] =	A[i] - A[i-1];
	for (int i = 0; i < N; i++)
		A[i] += 88;
}
bool ck(int x) {
	int mn, mx;
	if (sa[0]) {
		mn = sa[0];
		mx = sa[0];
	}
	for (int i = 1; i < N; i++) {
		if (height[i] >= x) {
			if (sa[i]) {
				mn = min(mn, sa[i]);
				mx = max(mx, sa[i]);
			}
		}
		else {
			if (mn+x < mx)
				return true;
			if (sa[i]) {
				mn = sa[i];
				mx = sa[i];
			}
		}
	}
	if (mn+x < mx)
		return true;
	return false;
}
void work() {
	int l = 0, r = N-1;
	int md;
	while (r-l>1) {
		md = l+r>>1;
		if (ck(md))
			l = md;
		else
			r = md;
	}
	if (ck(r))
		l = r;
	if (l+l >= 5)
		printf("%d\n", l+1);
	else
		printf("0\n");
}
int main() {
	freopen("theme.in", "r", stdin);
	freopen("theme.out", "w", stdout);
	rin();
	tps = Nmax;
	get_sa();
	get_rank();
	get_height();
	work();
	return 0;
}
//UBWH