TOI13: Orchid

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;

int orchids[N + 10], lis[N + 10];
int nOrchid;

int main(){

    scanf("%d", &nOrchid);
    for(int i = 1; i <= nOrchid; ++i){
        scanf("%d", &orchids[i]);
    }

    lis[0] = -1e9;
    int mxLen = 0;
    for(int i = 1; i <= nOrchid; ++i){
        int *ptr = upper_bound(lis, lis + mxLen + 1, orchids[i]);
        *ptr = orchids[i];
        mxLen = max(mxLen, (int)(ptr - lis));
    }

    cout << nOrchid - mxLen;

    return 0;
}