UOJ Logo Universal Online Judge

UOJ

#174. 新年的破栈

统计

零点的钟声敲响,猴年终于到来啦~

在这新年的第一天,猴族首领猴腮雷自然是要接受来自世界各地的朝贡的。在种类繁多的礼品中,魔仙堡女王送来的栈引起了他的注意——他发现这个栈的大小正好适合来装他的腮雷。

但是遗憾的是,因为种种原因,这个栈的底部破了,所以猴族首领猴腮雷让手下的工匠在这个栈的底部装了一个阀门,于是猴族首领猴腮雷不仅可以从这个栈的顶端取出它的腮雷,还能打开栈底的阀门,从最下面取出腮雷!

猴族首领猴腮雷有 $n$ 个腮雷,编号为 $i$ 的腮雷的威力是 $A_i$,而且任意两颗腮雷的威力都是不同的。现在他想用这个栈来整理这些腮雷,每时每刻他可以进行下面三种操作中的一种:

  1. 入栈:如果当前还有腮雷没有被放入过栈中,那么就把剩下的腮雷中编号最小的放到栈中(作为新的栈顶)。
  2. 出栈:如果当前栈中有腮雷,那么就把栈顶(即栈中最后被放入的)的腮雷取出来。
  3. 打开阀门:如果当前栈中有腮雷,那么就把栈底(即栈中最先被放入的)的腮雷取出来。

在所有腮雷都从栈中取出后,猴腮雷按照腮雷出栈的时间顺序排成一排,再把这些腮雷的威力记录下来,这样就得到了一个数列 $B$。现在猴腮雷想让这个数列的字典序尽可能的小,但是因为他日理万机,没有时间来想这种简单的小问题,于是他就让你来帮他求出字典序最小的数列 $B$。

对于两个长度为 $n$ 的数列 $a$ 和 $b$,$a$ 的字典序小于 $b$ 当且仅当存在一个整数 $k \in [1,n]$ 满足 $a_{i} = b_{i}(1 \leq i < k)$ 且 $a_k < b_k$。

输入格式

第一行一个正整数 $T$,表示数据组数。

对于每组数据,第一行包含一个正整数 $n$。

接下来一行 $n$ 个正整数 $A_1, \dots, A_n$。

输出格式

对于每组数据,输出一行 $n$ 个正整数,表示字典序最小的数列 $B$ 。

样例一

input

2
3
1 2 3
4
1 3 4 2

output

1 2 3
1 2 3 4

explanation

对于第一组数据,重复入栈、出栈这两个操作三次,即可得到最优解。

对于第二组数据,最优的操作序列如下:入栈,出栈,入栈,入栈,入栈,出栈,打开阀门,出栈。

样例二

见样例数据下载。

限制与约定

测试点编号$n$ 的规模
1$n \leq 10$
2
3$n \leq 2000$
4
5
6
7$n \leq 100000$
8
9
10

对于所有数据,保证 $1 \leq T \leq 5$,$1 \leq A_i \leq 10^9$ 。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载