class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # we scan the nums left to right,
        # use `end[i]` to record 'what is the minimum ending number of length `i`',
        #
        # how to maintenance `end`:
        # while scanning, updating the current number to accroding position of `end`
        # if end[i] < cur: end[i + 1] = min(end[i + 1], cur)
        # but i + 1 will overflow, so append when overflow
        #
        # python array is 0-based, above index of end will minus 1

        end = []
        for cur in nums:
            # find right-most i s.t. end[i] < cur
            # return -1 if no one
            i = self.find(end, cur)
            if i == len(end) - 1:
                end.append(cur)
            else:
                end[i + 1] = min(end[i + 1], cur)
        return len(end)

    def find(self, arr, target):
        # find right-most i s.t. end[i] < cur
        # return -1 if no one
        # invariant: left <= ret <= right

        left, right = -1, len(arr) - 1
        while left < right:

            # 2.5 rounding to 2 or 3?
            # should check when left + 1 == right and the if-statement won't result in a deadloop
            # when left + 1 == right, mid here will be right, both branch shrink

            # here left is initiated -1 which is not in a legal range, carefully think of underflow
            # when underflow, left and right must be both -1, so wo could return here
            mid = (left + right + 1) // 2
            if mid == -1:
                return -1
            if arr[mid] < target:
                left = mid # ans in [mid, right]
            else:
                right = mid - 1 # and in [left, mid - 1]

        return left