PROG-T1151: Tree

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

const int N = 2e5;

int lis[N + 1];

int main(){

    int nTree;
    scanf("%d", &nTree);
    int mxLen = 0;
    for(int i = 1; i <= nTree; ++i){
        int x;
        scanf("%d", &x);
        lis[mxLen + 1] = 1e9;
        int l = 1;
        int r = mxLen + 1;
        int ans = mxLen + 1;
        while(l <= r){
            int m = (l + r) / 2;
            if(lis[m] >= x){
                ans = min(ans, m);
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        lis[ans] = x;
        if(ans == mxLen + 1){
            ++mxLen;
        }
    }
    cout << mxLen;

    return 0;
}