patient sort + 记录前驱位置

class Solution:
    def LIS(self, arr):
        stack = [0]
        n = len(arr)
        pre = [-1] * n
        for i in range(1, n):
            if arr[i] > arr[stack[-1]]:
                stack.append(i)
                pre[i] = stack[-2]
            else:
                left, right = 0, len(stack)
                while left < right:
                    mid = left + (right - left) // 2
                    if arr[stack[mid]] < arr[i]:
                        left = mid + 1
                    else:
                        right = mid
                stack[left] = i
                pre[i] = stack[left - 1] if left - 1 >= 0 else -1

        idx = stack[-1]
        res = []
        while idx != -1:
            res = [str(arr[idx])] + res
            idx = pre[idx]
        return res

n = input()
arr = list(map(int, input().strip().split()))
res = Solution().LIS(arr)
print(' '.join(res))