#NC14893. 栈和排序
栈和排序
题目描述
给定一个从 到 的排列 ,以及一个空栈。你按顺序将排列中的元素依次入栈,可以在任意时刻选择将栈顶元素出栈并将其加入输出序列。入栈顺序不可改变。
理想情况下,你想得到一个严格从大到小排序的输出序列 ,但受栈操作限制可能无法实现。当无法完全排序时,请输出字典序最大的合法出栈序列。
输入格式
在一行中输入一个整数 。
第二行输入 个整数,表示排列 中的元素,用空格分隔。保证给出的是一个从 到 的排列。
输出格式
输出一行,包含若干整数,表示最终的出栈序列,用空格分隔,结尾不输出多余空格。
样例 1
5
2 1 5 3 4
5 4 3 1 2
样例说明
入栈顺序和操作示例如下:
2 入栈;
1 入栈;
5 入栈;
5 出栈;
3 入栈;
4 入栈;
4 出栈;
3 出栈;
1 出栈;
2 出栈。