#include<cstdio>
#define N 5001
int a[N],p[N],i,j,k,m,n,b[N],c,t,l,r; 
int main()
{FILE *f=fopen("secv.in","r"),*g=fopen("secv.out","w");
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
       {fscanf(f,"%d",&a[i]);
       if(a[b[m]]<a[i])
              p[i]=b[m],b[++m]=i;
       for(j=0,k=m;j<k;)
              {c=(j+k)/2;
              if(a[b[c]]<a[i])
                        j=c+1;
              else
                        k=c;}
       if(a[i]<a[b[j]])
              {if(j)
                        p[i]=b[j-1];
              b[j]=i;}}
for(i=m,j=b[m];i--;j=p[j])
       b[i]=j;
for(l=m-1;l>=0;l--)
       {for(k=t=0,i=b[0];i<=b[l]&&!t;i++)
              {for(c=j=0;j<m&&!c;j++)
              if(a[b[j]]==a[i])
                      k++,c=1;
              if(!c)
                      t=1;}
       if(r<k&&!t)
              r=k;}
fprintf(g,"%d",r?r:-1);
return 0;}