题解 | 栈和排序

import sys


def main():
    # 高效读取输入（适配n=1e6的大规模场景）
    data = sys.stdin.read().split()
    n = int(data[0])
    P = list(map(int, data[1 : n + 1]))

    # 1. 预处理后缀最大值数组：suffix_max[i]表示P[i..n-1]的最大值
    suffix_max = [0] * n
    suffix_max[-1] = P[-1]
    for i in range(n - 2, -1, -1):
        suffix_max[i] = max(P[i], suffix_max[i + 1])

    # 2. 栈模拟操作
    stack = []
    res = []
    for i in range(n):
        # 当前元素入栈
        stack.append(P[i])
        # 出栈判断：后续无更大元素（或已无后续元素），则出栈
        while stack and (i == n - 1 or suffix_max[i + 1] <= stack[-1]):
            res.append(str(stack.pop()))

    # 3. 输出结果（无多余空格）
    print(" ".join(res))


if __name__ == "__main__":
    main()