#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
using ll = long long;
using namespace std;
const int INF = 1e9;

int main() {

    int N;
    cin >> N;
    vector<int> A(N), dp(N, INF);
    rep(i, N) cin >> A[i];

    rep(i, N) * lower_bound(dp.begin(), dp.end(), A[i]) = A[i];

    cout << lower_bound(dp.begin(), dp.end(), INF) - dp.begin() << endl;

    return 0;
}
