记录在前边：

这是在浪费时间，但是还是想写一下，今天心情不好

分析：

利用二分找到小于等于a[i]的第一个数，那么f[l]后面的第一个数一定是大于等于a[i]的
这时f[r+1]=a[i]，为什么呢，例如：1 3 2，a[i]=2,那么3这个数就是占位的，用2替换掉3，
这样使得f[]这个数组是单调递增的，后续的a[i]如果大于里边的所有数就直接添入f[]

注意：不可以直接寻找大于等于a[i]的第一个数，这样最后的sum=max(sum,r+1);,f[r+1]=a[i];形式
不好确定，自己可以试一下。

代码：

#include<iostream>
using namespace std;
const int N=100010;
int f[N];
int a[N];
int main(){

    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        int l=0;
        int r=sum;
        while(l<r){
            int mid=(l+r+1)/2;
            if(f[mid]<a[i])
            l=mid;
            else
            r=mid-1;

        }

        sum=max(sum,r+1);
        f[r+1]=a[i];
    }
    cout<<sum<<endl;
    return 0;
}