[2,3,5,7], 4
我们要变成 [2, 3, 4, 7] 就是说要找到5的下标进行替换

[start, end] 有可能是 [3,5]  [5,7] 但是不关键
因为如果先判断start，后判断end, 哪个比4大就是目标值 

def main():
    # 获取数据
    length = int(input())
    nums = list(map(int, input().split()))

    #本体 : 更新res数组(单调递增), 最后返回res的长度
    if not nums:
        return 0
    res = []
    res.append(nums[0])
    for n in nums:
        # 如果比最后一个数还大, res就往后加, 不然就得替换掉某个位置
        if n > res[-1]:
            res.append(n)
        else:
            pos = bs(res, n, len(res) - 1)
            res[pos] = n

    print(len(res))

def bs(A, target, n):
    start , end = 0, n 
    while start + 1 < end:
        mid = (start + end) // 2
        if target > A[mid]: # > 还是 >= 都无所谓
            start = mid
        else:
            end = mid 
    # 最后只剩两个数[start, end]
    if A[start] >= target:
        return start
    if A[end] >= target:
        return end

main()