#include <bits/stdc++.h> using namespace std; const int N=100001; int a[N],dp[N]; int n,ans=0; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { if(a[i]>dp[ans]) { ans++; dp[ans]=a[i]; } else { int l=1,r=ans,mid; while(l<r) { mid=(l+r)/2; if(a[i]<=dp[mid]) { r=mid; } else { l=mid+1; } } dp[l]=a[i]; } } cout<<n-ans<<endl; return 0; }