#include <iostream>
#include <string>
#include <vector>




using namespace std;

template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
{
    ForwardIt it;
    typename iterator_traits<ForwardIt>::difference_type count, step;
    count = distance(first, last);

    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (!(value < *it)) {
            first = ++it;
            count -= step + 1;
        }
        else
            count = step;
    }
    return first;
}


const int MOD = 1e6 + 7;


void VIVOD(vector<vector<int> > vec2, int n, int m)
{
    for (auto i = 0; i < n; ++i)
    {
        for (auto j = 0; j < m; ++j)
        {
            cout << vec2[i][j] << " ";
        }
        cout << endl;
    }
}

int m(char c1, char c2)
{
    if (c1 == c2)
        return 0;
    return 1;
}


int main()
{

    int n, o = 1, w = 0, q = 0;
    cin >> n;
    vector<int> vec(n + 1, 0), vec2(n + 1, 0), ans, a(n + 1), vec3(n + 1, 0);
    vec2[0] = -1;
    vec[0] = -100001;
    for (auto i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    for (auto i = 1; i <= n; i++)
    {
        vec[i] = MOD;
    }
    for (auto i = 0; i < n; i++)
    {
        auto j = upper_bound(vec.begin(), vec.end(), a[i]);
        q = j - vec.begin();
        if (vec[q - 1] < a[i] && a[i] < vec[q])
        {
            vec[q] = a[i];
            vec2[q] = i;
            vec3[i] = vec2[q - 1];
            w = max(w, q);
            o = vec2[w];
        }
    }
    while (o != -1)
    {
        ans.push_back(a[o]);
        o = vec3[o];
    }
    cout << ans.size();
}
/*
EXPONENTIAL
POLYNOMIAL
41 83 67 35 71 43
*/