#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 1e6 + 5;
int A[maxn];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, thetich, dem = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> thetich;
        int it = lower_bound(A + 1, A + dem + 1, thetich) - A;
        if (it > dem) {
            dem++;
            A[dem] = thetich;
        }
        else{
            A[it] = thetich;
        }
    }
    cout << dem;
}
 
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSB1bGwgdW5zaWduZWQgbG9uZyBsb25nCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSwgeC5lbmQoKQp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjb25zdCBpbnQgbWF4biA9IDFlNiArIDU7CmludCBBW21heG5dOwppbnQgbWFpbigpIHsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwogICAgaW50IG4sIHRoZXRpY2gsIGRlbSA9IDA7CiAgICBjaW4gPj4gbjsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47ICsraSkgewogICAgICAgIGNpbiA+PiB0aGV0aWNoOwogICAgICAgIGludCBpdCA9IGxvd2VyX2JvdW5kKEEgKyAxLCBBICsgZGVtICsgMSwgdGhldGljaCkgLSBBOwogICAgICAgIGlmIChpdCA+IGRlbSkgewogICAgICAgICAgICBkZW0rKzsKICAgICAgICAgICAgQVtkZW1dID0gdGhldGljaDsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgQVtpdF0gPSB0aGV0aWNoOwogICAgICAgIH0KICAgIH0KICAgIGNvdXQgPDwgZGVtOwp9Cgo=

NQo0IDUgMyAyIDYK

5
4 5 3 2 6