基于循环不变量，正确性有保障，边界不再用特判。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        seq = []
        for x in nums:
            # find last seq[i] < x, replace seq[i + 1]
            # loop invariant: [0, l] < x and [r, n - 1] >= x
            # init: l = -1, r = n
            # end: l + 1 == r
            n = len(seq)
            l, r = -1, n
            while l + 1 < r:
                m = (l + r) // 2
                if seq[m] < x:
                    l = m
                else:
                    r = m
            if r == n:
                seq.append(x)
            else:
                seq[l + 1] = min(x, seq[l + 1])
        return len(seq)