#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e6+5;
int a[maxn];
int n;
int lis[maxn];
int len=1;
int find(int x){
    int l=1,r=len,m;
    while(l<r){
        m=l+(r-l)/2;
        if(lis[m]>=a[x]){//这里若去掉等号即为 非严格递增序列 
            r=m;
        } 
        else{
            l=m+1;
        }
    }
    return l;
}
int main(void){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    lis[1]=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]>lis[len]){
            lis[++len]=a[i];
        }
        else{
            int pos=find(i);
            lis[pos]=a[i];
        }
    }
    printf("%d",n-len+1);
    return 0;
}