vector<int> a;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        
        vector<int>::iterator it;
        it = lower_bound(a.begin(), a.end(), x);
        if (it != a.end()) *it = x;
        else a.push_back(x);
    }
 
    cout << a.size();

struct fentree {
    /// one based
    int n = 0;
    vector<ll> mx;

    void init(int lim, int val = 0) {
        n = lim;
        mx.assign(lim + 1, val);
    }
    fentree (int __n = 0, int __v = 0) { init(__n, __v); }

    void update_head(int p, ll v) {
        for (; p > 0; p -= p & -p)
            maximize(mx[p], v);
    }

    void update_tail(int p, ll v) {
        for (; p <= n; p += p & -p)
            maximize(mx[p], v);
    }

    ll getValue_head(int p) {
        ll res = 0;
        for (; p > 0; p -= p & -p)
            maximize(res, mx[p]);

        return res;
    }

    ll getValue_tail(int p) {
        ll res = 0;
        for (; p <= n; p += p & -p)
            maximize(res, mx[p]);

        return res;
    }
};

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int ord = 1;
    set<int> S(all(a));
    hashmap<int, int> M;
    for (int x : S) M[x] = ord++;

    fentree t(n);
    ll res = 0;
    vector<ll> dp(n, 0);
    for (int i = 0; i < n; ++i)
    {
        int p = M[a[i]];
        ll x = t.getValue_head(p - 1) + 1;
        t.update_tail(p, x);
        maximize(res, x);
    }

    cout << res;
    return 0;
}

const int INF = 1e9;
int lis(const vector<int> &a)
{
    int n = a.size();
    vector<int> f(n), b(n);

    int res = 0;
    for (int i = 0; i < n; ++i) {
        b[i] = +INF;
        f[i] = lower_bound(b.begin(), b.begin() + res + 1, a[i]) - b.begin();
        res = max(res, f[i] + 1);
        b[f[i]] = a[i];          
    }
    return res;

    vector<int> LIS;
    while (n--)
    {
       if (f[n] == res)
       {
            LIS.emplace_back(a[n]);
            --res;
       }
    }

    reverse(all(LIS);
    return LIS.size();
}

vector<int> a, f, b;
int main()
{
    int n;
    cin >> n;

    int res = 0;
    for (int i = 0; i < n; ++i) {
        a.push_back(readInt());
        b.push_back(+INF);
        f.push_back(lower_bound(b.begin(), b.begin() + res + 1, a[i]) - b.begin());
        maximize(res, f[i]);
        b[f[i]] = a[i];
    }

    cout << res + 1;
    return 0;
}