/*
TASK:psort
LANG:C++
*/

#include <stdio.h>

#define MAX 60000;

long f[50001], seq[50001], n, m, i, j;

int main () {

//freopen("psort.txt", "r", stdin);

scanf("%ld", &n);

for (i=1; i<=n; i++) {
  scanf("%ld", &seq[i]);
  f[i] = MAX;
  }

f[1] = seq[1];
m = 1;

for (i=2; i<=n; i++)
  if (seq[i] > f[m]) {
     m++;
     f[m] = seq[i];
     } else {
       for (j=m; j>=1; j--)
         if (f[j] > seq[i] && f[j-1] < seq[i]) f[j] = seq[i];
       }

printf("%ld\n", n-m);

return 0;
}
