https://www.acmicpc.net/problem/3745
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;
int32_t main() {
fastio;
int n;
while(cin >> n){
vector<int> table(n),ans;
for(int i = 0; i < n; i++) cin >> table[i];
for(int i = 0; i < n; i++){
if(ans.empty() || ans.back() < table[i]) ans.push_back(table[i]);
else *lower_bound(ans.begin(), ans.end(), table[i]) = table[i];
}
cout << ans.size() << "\n";
}
}