https://www.acmicpc.net/problem/12015
#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; 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";
}
#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;
using pii = pair<int, int>;
struct maxSegTree {
int tree[1 << 21];
int sz = 1 << 20;
void construct() {
for (int i = sz - 1; i > 0; i--) {
tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
}
}
// 1 - indexed
void update(int i, int val) {
--i |= sz; tree[i] = val;
while (i >>= 1) {
tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
}
}
// [l, r]
int query(int l, int r) {
--l |= sz, --r |= sz;
int ret = 0;
while (l <= r) {
if (l & 1) ret = max(ret, tree[l++]);
if (~r & 1) ret = max(ret, tree[r--]);
l >>= 1, r >>= 1;
}
return ret;
}
} MaxST;
int32_t main() {
fastio;
int n; cin >> n;
vector<pii> v(n);
for(int i = 0; i < n; i++){
cin >> v[i].first;
v[i].second = i + 1;
}
sort(v.begin(), v.end(),[](pii a,pii b){
if(a.first != b.first) return a.first < b.first;
return a.second > b.second;
});
for(int i = 0; i < n; i++){
int idx = v[i].second;
int maxVal = 0;
if(idx != 1) maxVal = MaxST.query(1, idx - 1);
MaxST.update(idx, maxVal + 1);
}
cout << MaxST.tree[1] << "\n";
}