#include <iostream>
#include <cmath>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define f first
#define s second
vector<int> compress(int N, vector<int> v){
pair<int,int> arr[N];
for(int i=0;i<N;i++){
arr[i].f=v[i];
arr[i].s=i;
}
sort(arr,arr+N);
int bef=arr[0].f+1,cnt=-1;
for(int i=0;i<N;i++){
if(arr[i].f!=bef){
cnt++;
bef=arr[i].f;
}
arr[i].f=arr[i].s;
arr[i].s=cnt;
}
vector<int> res;
sort(arr,arr+N);
for(int i=0;i<N;i++){
res.push_back(arr[i].s);
}
return res;
}
int LIS(int N, vector<int> v){ //N , compressed vector
set<int> se;
int zp=1<<(int)ceil(log2(N));
int seg[2*zp]={0};
se.insert(-1);
se.insert(N+1);
for(int i=0;i<N;i++){
auto lb=se.lower_bound(v[i]);
lb--;
if(*lb<0){
se.insert(v[i]);
int l=v[i]+zp;
seg[l]=max(seg[l],1);
l/=2;
// cout<<v[i]<<" "<<i<<" "<<1<<'\n';
while(l>=1){
seg[l]=max(seg[l+l],seg[l+l+1]);
l/=2;
}
continue;
}
else{
se.insert(v[i]);
int l=zp,r=(*lb)+zp;
int m=0;
while(l<=r){
if(l%2==1){
m=max(m,seg[l]);
l++;
}
if(r%2==0){
m=max(m,seg[r]);
r--;
}
l/=2;
r/=2;
}
m+=1;
r=v[i]+zp;
seg[r]=max(seg[r],m);
while(r>=1){
seg[r]=max(seg[r],m);
r/=2;
}
// cout<<v[i]<<" "<<i<<" "<<m<<'\n';
}
}
int m=0;
for(int i=0;i<2*zp;i++){
m=max(m,seg[i]);
}
return m;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("input.in","r",stdin);
int N;cin>>N;
vector<int> v(N);
for(int i=0;i<N;i++){
cin>>v[i];
}
v=compress(N,v);
int r = LIS(N,v);
cout<<r;
}
