//最長(zhǎng)遞增（非減少）子序列

//給定長(zhǎng)度尾部最小值遞推動(dòng)態(tài)規(guī)劃，O(nlogn)

#include<bits/stdc++.h>

using namespace std;

int main(){

? ? int n;

? ? cin>>n;

? ? vector<int> a;

? ? for(int i=0;i<n;i++){

? ? ? ? int x;

? ? ? ? cin>>x;

? ? ? ? auto ip=upper_bound(a.begin(),a.end(),x);

? ? ? ? if(ip==a.end()){//larger than anything ending

? ? ? ? ? ? a.push_back(x);

? ? ? ? }else{

? ? ? ? ? ? if(*ip>x){

? ? ? ? ? ? *ip=x;//replace larger minimal value

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? cout<<a.size()<<endl;

}