二分加dp
#include<bits\stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
int INF=1e9+7;
const int mod=1e9+7;
int n,m;
int x;
int g[50005];
int main(){
scanf("%d",&n);
int ans=1;
for(int i=1;i<=n;i++)g[i]=INF;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
if(i==1)g[i]=x;
else
{
int j=lower_bound(g+1,g+1+n,x)-g;
g[j]=x;
ans=max(ans,j);
}
}
printf("%d\n",ans);
return 0;
}
