/*
TASK: psort
LANG: C
*/
#include <stdio.h>

 int n,z;
 int a[65536];

 int main ()
  {
   int i,l,r,med,pom;
   scanf("%d",&n);
   z=0;
   for (i=1;i<=n;i++)
    {
     scanf("%d",&pom);
     l=1;
     r=z+1;
     while (1)
      {
       med=(l+r)/2;
       if (med==z+1) break;
       if (a[med]>pom && a[med-1]<pom) break;
       if (a[med]<pom)
        l=med+1;
         else
          r=med-1;
      }
     a[med]=pom;
     if (med==z+1) z++;
    }    
   printf("%d\n",n-z);
   return 0;
  }
  
