加了快读和快速输出qaq；

忽视它们吧；

开一个类似于栈的结构；

每进来一个数如果比栈顶大就直接进栈；

否则都向前找最近的比它小的数；

交换两者的值，ans++；

#include<bits/stdc++.h>
using namespace std;

int a[40005],b[40005];

void write(int x){
    if(x==0){putchar(48);return;}
    int len=0,dg[20];
    while(x>0){dg[++len]=x%10;x/=10;}
    for(int i=len;i>=1;i--)putchar(dg[i]+48);
}

inline bool read(int &num)  
{
        char in;bool IsN=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&(in<'0'||in>'9')) in=getchar();
        if(in=='-'){ IsN=true;num=0;}
        else num=in-'0';
        while(in=getchar(),in>='0'&&in<='9'){
                num*=10,num+=in-'0';
        }
        if(IsN) num=-num;
        return true;
}

int main()
{
    int n;
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    if(n==0){
        write('0\n');
        return 0;
    }
    b[1]=a[1];
    int len=1;
    for(int i=2;i<=n;i++){
        if(a[i]>=b[len]) b[++len]=a[i];
        else{
            int j=upper_bound(b+1,b+1+len,a[i])-b;
            b[j]=a[i];
        }
    }
    write(len);
    return 0;
}