TOI13: Orchid

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

const int INF = 2e9;
int dp[1000001];

int main(){

    int n;
    scanf("%d",&n);

    int sz = 0;

    for(int i=1;i<=n;i++){
        int x;
        scanf("%d", &x);

        if(x >= dp[sz]){
            dp[sz+1] = x;
            sz ++;
            continue;
        }

        int l = 1, r = sz, mid, mn = INF;
        while(l <= r){
            mid = (l + r) / 2;
            if(dp[mid] > x){
                mn = min(mn, mid);
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        dp[mn] = x;
    }

    printf("%d", n - sz);

    return 0;
}