#NC14893. 栈和排序

栈和排序

题目描述

给定一个从 11 到 nn 的排列 PP,以及一个空栈。你按顺序将排列中的元素依次入栈,可以在任意时刻选择将栈顶元素出栈并将其加入输出序列。入栈顺序不可改变。

理想情况下,你想得到一个严格从大到小排序的输出序列 n,n−1,…,1n, n-1, \dots,1,但受栈操作限制可能无法实现。当无法完全排序时,请输出字典序最大的合法出栈序列。

输入格式

在一行中输入一个整数 nn (1≤n≤106)\left(1 \leq n \leq 10^6\right)。

第二行输入 nn 个整数,表示排列 PP 中的元素,用空格分隔。保证给出的是一个从 11 到 nn 的排列。

输出格式

输出一行,包含若干整数,表示最终的出栈序列,用空格分隔,结尾不输出多余空格。

样例 1

5
2 1 5 3 4
5 4 3 1 2

样例说明

入栈顺序和操作示例如下:

2 入栈;

1 入栈;

5 入栈;

5 出栈;

3 入栈;

4 入栈;

4 出栈;

3 出栈;

1 出栈;

2 出栈。

来源

牛客原题