#include <bits/stdc++.h> using namespace std; int n,x[100005],Lis[100005],longest=0; int main() { cin>>n; for(int i=0; i<n; i++) { cin>>x[i]; if(!i) Lis[longest++]=x[i]; else { if(x[i]<Lis[longest-1]) { int j=upper_bound(Lis,Lis+longest,x[i])-Lis; Lis[j]=x[i]; } else { Lis[longest++]=x[i]; } } } cout<<longest; return 0; }