二分$(logN)$找第一个大于$a[i]$的位置
#include<bits/stdc++.h>
//unordered_map hash
//priority_queue<int,vector<int>,greater<int>>
//deque front和back
#define endl '\n'
#define PII pair<int,int>
//#define int long long
using namespace std;
inline int read();
int a[100005];
void solve(){
int n = read();
vector<int> v;
for(int i = 1; i <= n; ++ i){
a[i] = read();
}
int ans = 0;
for(int i = 1; i <= n; ++ i){
if(!v.size() || a[i] > v.back()) v.push_back(a[i]);
else{
int t = lower_bound(v.begin(),v.end(), a[i]) - v.begin();
v[t] = a[i];
}
if(v.size() > ans) ans = v.size();
}
cout << ans;
}
signed main(){
int _ = 1;
while(_ --) solve();
return 0;
}
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}