#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)

int main()
{
    int n; cin >> n;
    vector<int> a(n), groups;
    rep(i, n) cin >> a[i];

    groups.push_back(a[0]);
    rep(i, n-1){
        int ng = -1, ok = groups.size();
        while(ok - ng > 1){
            int mid = (ng + ok) / 2;
            if(groups[mid] < a[i + 1])
                ok = mid;
            else
                ng = mid;
        }
        if(ok == groups.size())
            groups.push_back(a[i + 1]);
        else
            groups[ok] = a[i + 1];
    }

    cout << groups.size() << endl;
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i];

    multiset<int> ms;
    for(auto a : A)
    {
        if(ms.empty() || *ms.begin() >= a) ms.insert(a);
        else
        {
            auto itr = ms.lower_bound(a);
            if(itr == ms.end() || *itr >= a) itr--;
            ms.erase(itr);
            ms.insert(a);
        }
    }
    cout << ms.size() << endl;

    return 0;
}
