#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define fi first #define sc second #define all(x) (x).begin(), (x).end() #define Bit(x, y) ((x >> y) & 1) #define inpFile(Task) freopen(Task".inp", "r", stdin); #define outFile(Task) freopen(Task".out", "w", stdout); #define submitFile(Task) inpFile(Task); outFile(Task); using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using ull = unsigned ll; const ll INF = (int)1e18, MOD1 = (int)1e9 + 7, MOD2 = (int)998244353; template<class X, class Y> void maximize(X &a, const Y &b) { a = (a < b) ? b : a; } template<class X, class Y> void minimize(X &a, const Y &b) { a = (a > b) ? b : a; } template<class T> void add(T& a, T b, T mod) { a += b; if(a >= mod) a -= mod; } template<class T> void sub(T& a, T b, T mod) { a -= b; if(a <= 0) a += mod; } int n, a[1000008]; signed main() { cin.tie(0)->ios_base::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; multiset<int> mts; int ans = 0; for(int i = 1; i <= n; i++) { auto it = mts.upper_bound(a[i]); if(it == mts.end()) { mts.insert(a[i]); ans++; } else { mts.erase(it); mts.insert(a[i]); } } cout << ans; cerr << "\nExecution time: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; return 0; }