#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,a[N],dp[N]; int len; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; dp[++len]=a[1]; for(int i=2;i<=n;i++) { if(a[i]>dp[len]) dp[++len]=a[i]; else { int pos=lower_bound(dp+1,dp+len+1,a[i])-dp; dp[pos]=a[i]; } } cout<<len; return 0; }