o21_oct_inc2

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int ar[N], lis[N];
int n, len;

int main(){

    scanf("%d", &n);

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

    lis[1] = ar[1];
    len = 1;
    for(int i=2;i<=n;i++){
        if(ar[i] > lis[len]){
            len ++;
            lis[len] = ar[i];
        }
        else{
            int l = 1, r = len, mn = len;
            while(l <= r){
                int mid = (l + r) / 2;
                if(lis[mid] >= ar[i]){
                    mn = min(mn, mid);
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            lis[mn] = ar[i];
        }
    }

    printf("%d\n", len);

    return 0;
}