cdq dp

constexpr int maxn=1e4+5;
struct node{int i,val,ans;};
void cdq(V<node>& v,int l,int r){
    if(r-l<=1) return;
    int m=(l+r)>>1;
    cdq(v,l,m);
    sort(v.begin()+l,v.begin()+m,[](node a,node b){
        return a.val<b.val;
        });
        sort(v.begin()+m,v.begin()+r,[](node a,node b){
                return a.val<b.val;
        });
    int lptr=l-1,curmax=0;
        for(int i=m;i<r;i++){
                while(lptr+1<m&&v[lptr+1].val<v[i].val)
                        curmax=max(curmax,v[++lptr].ans);
                if(lptr>=0&&v[lptr].val<v[i].val)
                        v[i].ans=max(v[i].ans,1+curmax);
        }
        sort(v.begin()+m,v.begin()+r,[](node a,node b){
                return a.i<b.i;
        });
        cdq(v,m,r);
}
static inline void solve(){
    int n;cin>>n;
    V<node> v(n);
    for(int i=0;i<n;i++)
                cin>>v[i].val,v[i].i=i,v[i].ans=1;
    cdq(v,0,n);
    sort(v.begin(),v.end(),[](node a,node b){
        return a.i<b.i;
    });
    int ans=0;
    for(auto i:v)
                ans=max(ans,i.ans);
    cout<<ans<<endl;
}