零点的钟声敲响，猴年终于到来啦~
在这新年的第一天，猴族首领猴腮雷自然是要接受来自世界各地的朝贡的。在种类繁多的礼品中，魔仙堡女王送来的栈引起了他的注意——他发现这个栈的大小正好适合来装他的腮雷。
但是遗憾的是，因为种种原因，这个栈的底部破了，所以猴族首领猴腮雷让手下的工匠在这个栈的底部装了一个阀门，于是猴族首领猴腮雷不仅可以从这个栈的顶端取出它的腮雷，还能打开栈底的阀门，从最下面取出腮雷！
猴族首领猴腮雷有 $n$ 个腮雷，编号为 $i$ 的腮雷的威力是 $A_i$，而且任意两颗腮雷的威力都是不同的。现在他想用这个栈来整理这些腮雷，每时每刻他可以进行下面三种操作中的一种：
在所有腮雷都从栈中取出后，猴腮雷按照腮雷出栈的时间顺序排成一排，再把这些腮雷的威力记录下来，这样就得到了一个数列 $B$。现在猴腮雷想让这个数列的字典序尽可能的小，但是因为他日理万机，没有时间来想这种简单的小问题，于是他就让你来帮他求出字典序最小的数列 $B$。
对于两个长度为 $n$ 的数列 $a$ 和 $b$，$a$ 的字典序小于 $b$ 当且仅当存在一个整数 $k \in [1, n]$ 满足 $a_i = b_i$ ($1 \leq i < k$) 且 $a_k < b_k$。
第一行一个包含正整数 $T$ ($T \leq 5$)，表示数据组数。
对于每组数据，第一行包含一个正整数 $n$ ($n \leq 10^5$)。
第二行包含 $n$ 个正整数 $A_1, \cdots, A_n$ ($1 \leq A_i \leq 10^9; A_i \neq A_j$)。
对于每组数据，输出一行 $n$ 个正整数，表示字典序最小的数列 $B$。
注意到字典序最小这种性质，这启发我们去使用贪心算法解决。
那具体地，如何贪心呢？由于 $A_i \neq A_j$ 且问题和绝对大小无关，因此不妨设 $\left\{ A_n \right\}$ 是一个 $1 \sim n$ 的排列。
首先可以注意到，最终排列 $B$ 的第一项一定是 $1$。因为我们总是可以不停入栈直到遇到 $1$ 再弹出。
由于贪心性质，第一项就是 $1$ 了。那么此时，第二项就有如下几种选择：
我们可以比较这三种方案哪一种可以得到最小的值，就将它作为 $B$ 的第二项。
以此类推，其实序列 $B$ 每一项 (包括第一项) 也可以用这种方法得到。
这就是这道题的贪心算法。那具体怎么实现呢？
我们看它需要用到哪些操作。首先你需要用两个有序表维护当前还在栈内的元素以及未入栈的元素。每次，需要比较栈顶 $t$，栈顶 $b$ 以及未入栈的元素中值最小的那个。
注意到未入栈的元素一定是序列 $A$ 的一个后缀。因此，只需要在一开始先维护一下 $A$ 序列的后缀最大值即可。
这样，由于每个元素至多入出栈两次，在未入栈的元素中最多被弹出一次，因此总时间复杂度为 $O(n)$。
#include <bits/stdc++.h>
#define N 100005
int n;
int a[N], min[N], stack[N];
void work() {
int i, j = 1, h = 0, t = 0;
scanf("%d", &n); min[n + 1] = INT_MAX;
for (i = 1; i <= n; ++i) scanf("%d", a + i);
for (i = n; i; --i) min[i] = std::min(a[i], min[i + 1]);
for (i = 1; i <= n; ++i)
if (h != t && (stack[h] < min[j] || stack[t - 1] < min[j]))
printf("%d%c", stack[h] < stack[t - 1] ? stack[h++] : stack[--t], i == n ? 10 : 32);
else {
printf("%d%c", min[j], i == n ? 10 : 32);
for (; a[j] != min[j]; ++j) stack[t++] = a[j]; ++j;
}
}
int main() {
int T;
for (scanf("%d", &T); T; --T) work();
return 0;
}
坑1：注意栈空的情况，以及选择栈内元素的条件为 $\mathrm{or}$ 而不是 $\mathrm{and}$。