include<bits/stdc++.h>

define int long long

using namespace std;

const int N=1e6+6; int a[N],n,t[N]; signed main(){ freopen("CAU4.INP" , "r" , stdin); freopen("CAU4.OUT" , "w" , stdout); iosbase::syncwith_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=0;i<n;i++) cin>>a[i]; int len=0; for(int i=0;i<n;i++){ int l=0,r=len,pos=len+1; while(l<=r){ int mid=(l+r)/2; if(t[mid]>=a[i]){ pos=mid; r=mid-1; } else l=mid+1; } t[pos]=a[i]; if(pos>len) len=pos; } cout<<n-len; }