记录编号	220243	评测结果	AAAAAAAAAAAAAAA
题目名称	乐曲主题	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.066 s
提交时间	2016-01-17 18:35:07	内存使用	31.63 MiB

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
queue<int>q;
bool b[40010];
struct u
{
	u *e[87*2+1],*pre;
	int id;
}*rt,*ls;
int d[40010];
struct uyu
{
	int b;
	int x;
}c[4000100];
int r[40010];
int n,pr,id;
int z[40010],y[40010],h[40010],l;
inline void gj(int a,int b)
{
	c[++l].b=b;
	c[l].x=h[a];
	h[a]=l;
	r[b]++;
}
inline void gtrie(int a,int s)
{
	u *p=new u(),*k=ls;
	p->id=++id;
	d[p->id]=d[k->id]+1;
	while(k&&(!k->e[a]))
	{
		k->e[a]=p;
		k=k->pre;
	}
	if(!k)
	{
		p->pre=rt;
	}
	else
	{
		u *q=k->e[a];
		if(d[k->e[a]->id]==d[k->id]+1)
			p->pre=q;
		else
		{
			u *nq=new u();
			nq->id=++id;
			d[nq->id]=d[k->id]+1;
			nq->pre=q->pre;
			p->pre=q->pre=nq;
			memcpy(nq->e,q->e,sizeof(nq->e));
			while(k&&k->e[a]==q)
			{
				k->e[a]=nq;
				k=k->pre;
			}
		}
	}
	ls=p;
	//z[p->id]=y[p->id]=0;	
}
void g(u *k)
{
	b[k->id]=1;
	for(int i=0;i<=174;i++)
		if(k->e[i]!=NULL)
		{
			gj(k->e[i]->id,k->id);
			if(!b[k->e[i]->id])
				g(k->e[i]);
		}
}
inline void gmain()
{
	l=0;
	memset(z,0x3f,sizeof(z));
	memset(b,0,sizeof(b));
	memset(y,0,sizeof(y));
	memset(h,0,sizeof(h));
	rt=new u();
	id=0;
	rt->id=++id;
	ls=rt;
	pr=0;
	int o,oo;
	scanf("%d",&o);
	for(int i=2;i<=n;i++)
	{
		scanf("%d",&oo);
		gtrie(oo-o+87,i);
		o=oo;
	}
	g(rt);
	while(ls)
	{
		z[ls->id]=y[ls->id]=1;
		ls=ls->pre;
	}
	for(int i=1;i<=id;i++)
	{
		if(r[i]==0)
		{
			q.push(i);
			z[i]=y[i]=1;
			//printf("E%d ",i);
		}
		/*
		if(r[i]>0)
			printf("O%d\n",i);*/
	}
	//printf("d%d",id);
	while(!q.empty())
	{
		int k=q.front();
		if(pr<min(d[k]+1,y[k]-z[k]))
			pr=min(d[k]+1,y[k]-z[k]);
		q.pop();
		for(int i=h[k];i;i=c[i].x)
		{
			int u=c[i].b;
			r[u]--;
			if(y[u]<y[k]+1)
				y[u]=y[k]+1;
			if(z[u]>z[k]+1)
				z[u]=z[k]+1;
			if(r[u]==0)
				q.push(u);
		}
	}
	if(pr<5)
		pr=0;
	printf("%d\n",pr);
}
int main()
{
	freopen("theme.in","r",stdin);
	freopen("theme.out","w",stdout);
	while(~scanf("%d",&n))
	{
		if(n==0)
			return 0;
		gmain();
	}
}