a[N] 输入的序列
q[N] q[i] 表示长度为i的严格单调上升序列的结尾最小值

遍历a[N]
用二分法找当前长度len中 q[0]到q[len]中小于a[i]的最大值，更新q[r+1], 同时更新len

以

7
3 1 2 1 8 5 6

为例
q[1] = 3 len = 1
q[1] = 1 len = 1
q[2] = 2 len = 2
q[3] = 8 len = 3
q[3] = 5 len = 3
q[4] = 6 len = 4

后更新的数字是否影响结果？
答： 不会， 比如 1 3 6 2
最终q[n] 是 1 2 6 ，但是实际序列 是1 3 6 ，但是 1 3 6 还是 1 2 6 长度都是3，
更新了小于len的位置， 最多是没有后续，比如q[n] 更新到1 2 6停止了
但是len是3 （来自 1 3 6）是没有问题的

#include <iostream>

using namespace std;

const int N = 100010;

int a[N], q[N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int len = 0;
    for (int i = 0; i < n; ++i) {
        int l = 0, r= len;
        while (l < r) {
           int mid = l + r + 1 >> 1;
           if (q[mid] < a[i]) l = mid;
           else r = mid - 1;
        }
        len = max(len , r + 1);
        q[r + 1] = a[i];
    }

    cout << len << endl;
}