#include <iostream>
#include <cstring>
using namespace std;
const int N=500010;
int a[N],dp[N];
int n;
int LIS()
{
dp[1]=a[1];
int len=1;
for(int i=2;i<=n;i++)
{
int left=1; int right=len;
while(left<=right)
{
int m=(left+right)/2;
if(a[i]>dp[m])
left=m+1;
else
right=m-1;
}
dp[left]=a[i];
if(len<left)
len=left;
}
return len;
}
int main()
{
while(cin>>n)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int ans=LIS();
printf("%d\n",ans);
}
return 0;
}