#include<cstdio>
#include<cstring>
int a[5001],i,j,k,m,n,b[5001],s,p[5001],l[5001],f,h,t,d[5001],o,e=5001,g,u[5001];
int main()
{
    freopen("secv.in","r",stdin),
    freopen("secv.out","w",stdout),
    scanf("%d",&n);
    for(f=i=1;i<=n;i++)
          scanf("%d",a+i),d[i]=-1,p[i]=5001;
    while(1)
    {
          if(f>=n)
               break;
          memset(l,0,sizeof(l));
          for(l[n]=1,i=n-1;i>=f;i--)
          {
               for(m=0,j=i+1;j<=n;j++)
               if(l[j]>m&&a[j]>a[i])
                    m=l[j];
               l[i]=m+1;
          }
          m=l[f],t=f;
          for(i=f+1;i<=n;i++)
          if(l[i]>m)
               m=l[i],t=i;
          o=0,b[++o]=t;
          for(i=t+1;i<=n;i++)
          if(a[i]>a[b[o]]&&l[i]==m-1)
               b[++o]=i,m--;
          for(s=f;s<=b[o];s++)
          for(j=1;j<=o;j++)
          if(a[s]==a[b[j]])
               d[s]=j;
          for(j=b[o];j>f&&d[j]>d[j-1];j--);
          for(s=j;s<=b[o];s++)
               p[s]=b[o]-s+1;
          for(s=f;s<j;s++)
          {
               for(h=0,k=1;k<=o&&b[k]<s;k++);
               for(t=s;t<b[o]&&!h;t++)
               if(d[t]<d[b[k]])
                     h=1;
               p[s]=!h?(b[o]-s+1):5001;
          }
          for(e=5001,j=f;j<=b[o]&&p[j]!=5001;j++)
          if(p[j]<e)
               e=p[j];
          u[++g]=e,f=b[o]+1;
    }
    for(e=u[1],i=2;i<=g;i++)
    if(e<u[i])
          e=u[i];
    printf("%d",e);
}