#include <stdio.h>
#define infinit 1000005
int lungime[5005],a[5005],solutie[5005],n;

void date(){
int i;
freopen ("subsir2.in","r",stdin);
scanf("%d\n",&n);
for(i=1;i<=n;i++)
scanf("%d ",&a[i]);
}

int main(){
  int i,j,min,pozmax;
  freopen("subsir2.out","w",stdout);
  date();
lungime[n]=1;

  for(i=n-1;i>0;i--){
  //starea i
  lungime[i]=1;
  for(j=i+1;j<=n;j++)
    if((lungime[i]<lungime[j]+1)&&(a[i]<a[j]))lungime[i]=lungime[j]+1;                  
  }
    
 
//cauta numarul minim
int k=2;
min=a[1];solutie[1]=lungime[1];
  for(i=2;i<=n;i++)
    {if(a[i]<min)min=a[i];solutie[k]=lungime[i];//printf("%d ",solutie[k]);}
    }
//afla minimul din solutie[]
min=solutie[1];
for(i=2;i<k;i++)
  if(min>solutie[i])min=solutie[i];
printf("%d\n",min);
return 0;
}