#include <bits/stdc++.h>
using namespace std;
int a[100100];
int f[100100];
int main() {
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }
    f[1]=a[1];
    int len=1;
    for(int i=2; i<=n; i++) {
        if(a[i] > f[len]) f[++len] = a[i];
        else {
            int l=1,r=len,mid;
            while(l < r) {
                mid=(l+r) / 2;
                if(a[i] <= f[mid]) r=mid;
                else l=mid+1;
            }
            f[l]=a[i];
        }
    }
    cout<<n-len;
}
 


/**************************************************************
	Problem: 1277
	User: zhengzihao
	Language: C++
	Result: Wrong Answer
****************************************************************/