#include<stdio.h>

#define minim( x , y )  ( x < y ? x : y )

#define Nmax 5001

int v[Nmax],a[Nmax],t[Nmax],viz[Nmax],n;

int main()
{

int i,j,min,S;

freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);

scanf("%d",&n);

for(i=1;i<=n;i++)
 scanf("%d",v+i);

 a[n]=1;t[n]=0;

 for(i=n-1;i;i--)
  {
  min=10001;
  a[i]=5001;

    for(j=i+1;j<=n;j++)
   {
   if( v[i] <= v[j] && v[j] < min )
      if ( a[i] > a[j]+1 )
	a[i] = a[j] + 1, t[i] = j;

   if( v[j] >= v[i] ) min= minim(min,v[j]);
   }

  if( a[i] == 5001 ) a[i] = 1, t[i] = i;

  }


  S=5001;

  for(i=1;i<=n;i++)
   if ( !viz[i] && a[i] <= S )
    {
    for(j=i+1;j<=n;j++)
      if( v[j]>=v[i]) viz[j]=1;
      S = a[i] ;
     }



  printf("%d\n",S);
  return 0;
  }