#include <bits/stdc++.h>
using namespace std;

using i8  = int8_t;using i16 = int16_t;using i32 = int32_t;using i64 = int64_t;using u8  = uint8_t;using u16 = uint16_t;using u32 = uint32_t;using u64 = uint64_t;using f32 = float;using f64 = double;
using vi32 = vector<i32>;using vi64 = vector<i64>;using vvi32 = vector<vi32>;using vvi64 = vector<vi64>;using pi32 = pair<i32,i32>;using pi64 = pair<i64,i64>;

#define FOR(i,a,b) for(i64 i=(a), i##_len=(b); i<i##_len; ++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,x) for(i64 i=1;i<=(i64)(x);i++)
#define RREPS(i,x) for(i64 i=((i64)(x));i>0;i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define SZ(x) ((i64)(x).size())
#define CLR(ar,val) memset(ar, val, sizeof(ar))
#define cauto const auto&
#define pb push_back
#define mp make_pair
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

i32 dx[4]={1,0,-1,0};
i32 dy[4]={0,1,0,-1};
const i32 INF32 = 0x3F3F3F3F;
const i64 INF64 = 0x3F3F3F3F3F3F3F3F;
const i32 MOD   = 1000000007;

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

/// pair vectorに対して直接入出力できるようにする
template<typename A, typename B> istream &operator>>(istream &is, pair<A, B> &p) { is >> p.first >> p.second;return is; }
template<typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B>& p) { os << p.first << ' ' << p.second;return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for(T& in : v) is >> in; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for(i32 i = 0; i < (i32)v.size(); i++) os << v[i] << (i+1 != (i32)v.size() ? " " : ""); return os; }

/// # 配列のk個ずつの最小値を求める
///
/// ```c++:slide minimum
///   vector<i32> A = {0,1,2,3,2,1,2,3,4,3,2,1,0};
///   auto B = slideMin(A, 4);
///   //B == {0,1,1,1,1,1,2,2,1,0}
/// ```
template<typename T>
vector<T> slideMin(const vector<T>& v, i32 k) {
    deque<i32> deq;
    vector<T> ret;
    for(i32 i=0;i < (i32)v.size(); i++) {
        while(!deq.empty() && v[deq.back()] >= v[i]) {
            deq.pop_back();
        }
        deq.push_back(i);
        if (i - k + 1 >= 0) {
            ret.emplace_back(v[deq.front()]);
            if (deq.front() == i - k + 1) deq.pop_front();
        }
    }
    return ret;
}

/// # 累積和を計算する
///
/// ## 初期化
/// ```c++
///   CumulativeSum<i64> A(sz);
/// ```
///
/// ## インデックスkに値vを加える
/// ```c++
///   A.add(k,v);
/// ```
///
/// ## 累積和を構築
/// ```c++
///   A.build();
/// ```
///
/// ## 配列を表示
/// ```c++
///   A.printf();
/// ```
///
/// ## 閉区間[0,k]の和を計算
/// ```c++
///   A.query(k);
/// ```
template<class T>
struct CumulativeSum {
    vector<T> dat;
    CumulativeSum(i32 sz) : dat(sz, 0) { };

    void add(i32 k, T x) {
        dat[k] += x;
    }

    void build() {
        for (i32 i = 1; i < (i32)dat.size(); i++) {
            dat[i] += dat[i-1];
        }
    }

    void printf() {
        for (i32 i = 0; i < (i32)dat.size(); i++) {
            if (i == 0) {
                cout << "[" << dat[i];
            } else if (i == ((i32)dat.size() - 1)) {
                cout << ", " << dat[i] << "]" << endl;
            } else {
                cout << ", " << dat[i];
            }
        }
    }

    T query(i64 k) {
        if (k < 0) return 0;
        return (dat[min(k, (i64)(dat.size() - 1))]);
    }
};
/// 累積和の2次元版
template<class T>
struct CumulativeSum2D {
    vector<vector<T>> dat;
    CumulativeSum2D(i32 w, i32 h) : dat(w + 1, vector<T>(h + 1, 0)) { }

    void add(i32 x, i32 y, T z) {
        ++x; ++y;
        if (x >= SZ(dat) || y >= (SZ(dat[0]))) return;
        dat[x][y] += z;
    }

    void build() {
        for (i32 i = 1; i < SZ(dat); i++) {
            for (i32 j = 1; j < SZ(dat[i]); j++) {
                dat[i][j] += dat[i][j-1] + dat[i - 1][j] - dat[i - 1][j - 1];
            }
        }
    }

    void printf() {
        for (i32 i = 0; i < SZ(dat); i++) {
            for (i32 j = 0; j < SZ(dat[i]); j++) {
                cout << dat[i][j] << (j == (SZ(dat[i]) - 1) ? "" : " ");
            }
            cout << endl;
        }
    }

    T query(i32 sx, i32 sy, i32 gx, i32 gy) {
        return (dat[gx][gy] - dat[sx][gy] - dat[gx][sy] + dat[sx][sy]);
    }
};

/// # 最長増加部分列 (LIS)
/// a      : 数列aの最長増加部分列の長さを求める
/// strict : trueのとき狭義単調増加列 falseのとき広義単調増加列
template<typename T>
size_t longest_increasing_subsequence(const vector<T> &a, bool strict) {
    vector<T> lis;
    for (auto &p : a){
        typename vector<T>::iterator it;
        if (strict) it = lower_bound(begin(lis), end(lis), p);
        else it = upper_bound(begin(lis), end(lis), p);
        if (end(lis) == it) lis.emplace_back(p);
        else *it = p;
    }
    return lis.size();
}

/// # 個数制限付きナップザック問題 (O(NW))
/// w : i番目の重さの配列
/// m : i番目の品物をいくつまで選べるかの配列
/// v : i番目の品物の価値の配列
/// W : ナップザックの容量
/// NG: 容量として不適当な値 (-1や-INFなど、初期化のため)
template<typename T, typename Compare = greater<T>>
vector<T> knapsack_limitations(const vi32 &w, const vi32 &m, const vector<T> &v, const i32 &W, const T &NG, const Compare &comp = Compare()) {
    const i32 N = (i32) w.size();
    vector<T> dp(W+1, NG), deqv(W+1);
    dp[0] = T();
    vector<i32> deq(W+1);
    for(i32 i = 0; i < N; i++) {
        for (i32 a = 0; a < w[i]; a++) {
            i32 s = 0, t = 0;
            for (i32 j = 0; w[i] * j + a <= W; j++) {
                if (dp[w[i] * j + a] != NG) {
                    auto val = dp[w[i] * j + a] - j * v[i];
                    while(s < t && comp(val, deqv[t - 1])) --t;
                    deq[t] = j;
                    deqv[t++] = val;
                }
                if (s < t) {
                    dp[j*w[i]+a] = deqv[s] + j * v[i];
                    if (deq[s] == j - m[i]) ++s;
                }
            }
        }
    }
    return dp;    
}

/// # 個数制限付きナップザック問題 (O(N^2max(vi)^2))
/// w : i番目の重さの配列
/// m : i番目の品物をいくつまで選べるかの配列
/// v : i番目の品物の価値の配列
/// W : ナップザックの容量
template<typename T>
T knapsack_limitations2(const vector<T> &w, const vector<T> &m, const vector<i32> &v, const T &W) {
    const i32 N = (i32) w.size();
    auto v_max = *max_element(begin(v), end(v));
    if(v_max == 0) return 0;
    vector<i32> ma(N);
    vector<T> mb(N);
    for(i32 i = 0; i < N; i++) {
        ma[i] = min< T >(m[i], v_max - 1);
        mb[i] = m[i] - ma[i];
    }
    T sum = 0;
    for(i32 i = 0; i < N; i++) sum += ma[i] * v[i];
    auto dp = knapsack_limitations(v, ma, w, sum, T(-1), less<>());
    vector<i32> ord(N);
    iota(begin(ord), end(ord), 0);
    sort(begin(ord), end(ord), [&](i32 a, i32 b) { 
            return v[a] * w[b] > v[b] * w[a];
    });
    T ret = T();
    for(i32 i = 0; i < SZ(dp); i++) {
        if(dp[i] > W || dp[i] == -1) continue;
        T rest = W - dp[i], cost = i;
        for(auto &p : ord) {
            auto get = min(mb[p], rest / w[p]);
            if(get == 0) break;
            cost += get * v[p];
            rest -= get * w[p];
        }
        ret = max(ret, cost);
    }
    return ret;
}
void Main();
i32 main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(15);Main();return 0;}

void Main() {
    //-------------------------------------------------------------------------
int N;
cin >> N;
vector< int > A(N);
cin >> A;
cout << longest_increasing_subsequence(A, true) << endl;
    //-------------------------------------------------------------------------
}



Measured memory_bytes: 3788