#include <iostream>
#include <vector>
using namespace std;
int a[200005];
int getLISLength(int num[], int length) {
    vector<int> ivec;
    for (int i = 0; i < length; ++i) {
        if (ivec.size() == 0 || ivec.back() < num[i])
            ivec.push_back(num[i]);
        else {
            int low = 0, high = ivec.size() - 1;
            while (low < high) {
                int mid = (low + high) / 2;
                if (ivec[mid] < num[i])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            ivec[low] =  num[i];
        }
    }
    return ivec.size();
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    int ans =getLISLength(a,n);
    cout<<n-ans+1<<endl;


    return 0;
}
