This post is written in Chinese. Please consider using Google Translate

把原序列相邻每项做差，然后问题就转化成了求一个串的最长不重叠重复子串，且两个子串相距至少一位，可以用后缀数组做。

首先求出后缀数组和Height数组，Height[i]=LCP(SA[i],SA[i-1])。接下来二分答案A，判定A是否为可行解。判断方法是找出在Height数组中找出连续的一段Height[i..j]，使得i<=k<=j均满足Height[k]>=A，并且i-1<=k1,k2<=j中，要有Max{SA[k1]} - Min{SA[k2]} >= A + 1(距离相差至少1)，这时A是可行的。

后缀数组的分组思想十分重要，这道题就是一个经典应用，还应用到了求最长公共子串(LCS)问题。

/*
 * Problem: pku1743 Musical Theme (USACO 28)
 * Author: Guo Jiabao
 * Time: 2009.4.17 18:45
 * State: Solved
 * Memo: 后缀数组 最长重复子串
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=20011,INF=0x7FFFFFFF;
using namespace std;
struct SufficArray
{
    struct RadixElement
    {
        int id,k[2];
    }RE[MAXN],RT[MAXN],*R1,*R2;
    int N,A[MAXN],SA[MAXN],Rank[MAXN],Height[MAXN],C[MAXN];
    void RadixSort()
    {
        int i,y;
        for (y=1,R1=RE,R2=RT;y>=0;y--)
        {
            memset(C,0,sizeof(C));
            for (i=1;i<=N;i++) C[ R1[i].k[y] ]++;
            for (i=1;i<MAXN;i++) C[i]+=C[i-1];
            for (i=N;i>=1;i--) R2[ C[ R1[i].k[y] ]-- ]=R1[i];
            R1=RT,R2=RE;
        }
        for (i=1;i<=N;i++)
        {
            Rank[RE[i].id]=Rank[RE[i-1].id];
            if ( RE[i].k[0]!=RE[i-1].k[0] || RE[i].k[1]!=RE[i-1].k[1] )
                Rank[RE[i].id]++;
        }
    }
    void CalcSA()
    {
        int i,k;
        Rank[RE[0].id=0]=0;RE[0].k[0]=-1;
        for (i=1;i<=N;i++)
            RE[i].id=i,RE[i].k[0]=A[i],RE[i].k[1]=0;
        RadixSort();
        for (k=1;k+1<=N;k*=2)
        {
            for (i=1;i<=N;i++)
                RE[i].id=i,RE[i].k[0]=Rank[i],RE[i].k[1]=i+k<=N?Rank[i+k]:0;
            RadixSort();
        }
        for (i=1;i<=N;i++)
            SA[Rank[i]]=i;
    }
    void CalcHeight()
    {
        int i,k,h=0;
        for (i=1;i<=N;i++)
        {
            if (Rank[i]==1)
                h=0;
            else
            {
                k=SA[Rank[i]-1];
                if (h) h--;
                for (;A[i+h]==A[k+h];h++);
            }
            Height[Rank[i]]=h;
        }
    }
}SA;
int N,Ans;
bool check(int A)
{
    int i,j,Min,Max;
    for (i=1;i<=SA.N;i++)
    {
        if (SA.Height[i]>=A)
        {
            Min=Max=SA.SA[i-1];
            for (j=i;j<=SA.N && SA.Height[j]>=A;j++)
            {
                if (SA.SA[j]<Min)
                    Min = SA.SA[j];
                if (SA.SA[j]>Max)
                    Max = SA.SA[j];
            }
            j--;
            if (Max-Min>A)
                return true;
            i=j;
        }
    }
    return false;
}
void solve()
{
    int a,b,m;
    SA.CalcSA();
    SA.CalcHeight();
    a=0;b=SA.N;
    while (a+1<b)
    {
        m=(a+b)/2;
        if (check(m))
            a=m;
        else
            b=m-1;
    }
    if (check(b))
        a=b;
    Ans=a+1;
    if (Ans<5) Ans=0;
}
void init()
{
    int i,c,d,md=INF;
    memset(&SA,0,sizeof(SA));
    d=-100;
    for (i=1;i<=N;i++)
    {
        scanf("%d",&c);
        SA.A[++SA.N]=c-d;
        if (c-d<md)
            md=c-d;
        d=c;
    }
    md--;
    for (i=1;i<=N;i++)
        SA.A[i]-=md;
}
int main()
{
    freopen("theme.in","r",stdin);
    freopen("theme.out","w",stdout);
    while (scanf("%d",&N),N)
    {
        init();
        solve();
        printf("%dn",Ans);
    }
    return 0;
}