点击此处下载附加样例文件

题目描述

$N$ 个不超过 $N$ 的正整数从左向右排成一排，形成一个序列 $A$：$A_1, A_2, ……, A_N$。

现在，要从左向右把这些元素依次取出来。每取出一个元素 $A_i$，你可以把它扔掉，也可以把它放到 $A$ 序列的末尾，即最右端。

等到把原来的 $N$ 个元素全部取出并处理完后，你将得到一个新的 $A$ 序列。

你期望最终得到的 $A$ 序列的字典序最大。

另外，你可以在开始取出 $A_1$ 之前，任意选择原序列的某一个元素，将其移动到它左边的任意一个元素之前。

你也可以不这么操作。或者说，你最多只能做这样的操作一次。并且当你开始取数之后，你不能再做这样的操作。

请你输出最终能得到的字典序最大的 $A$ 序列。

多组数据。

注：对于两个序列 $A$ 和 $B$，序列 $A$ 的字典序大于序列 $B$，当且仅当满足下列两个条件之一：

• （1）对于 $A_i≠B_i$ 的最小的 $i$，有 $A_i > B_i$;
• （2）当不存在 $A_i≠B_i$ 的 $i$ 时，有 $|A| > |B|$ (其中 $|S|$ 表示序列 $S$ 的长度，即包含的元素个数)。

输入格式

第一行：一个整数 $T$，表示测试数据组数。

每组测试数据占两行：

• 第一行：一个整数 $N$
• 第二行：$N$ 个整数 $A_i$

输出格式

共 T 行，每组数据的答案占一行。

输入样例

3
3
3 2 1
4
1 2 3 4
5
5 1 3 1 4

输出样例

3 2 1
4 3
5 4 3 1

数据范围

10% 的数据：$N ≤ 100$。

20% 的数据：$N ≤ 1000$。

70% 的数据：$N ≤ 2 × 10^5$, 数据保证所有输入的 $N$ 之和 ≤ $10^6$。

100% 的数据：$1 ≤ T ≤ 100$, $1 ≤ N ≤ 2 × 10^5$, $1 ≤ A_i ≤ N$,
数据保证所有输入的 $N$ 之和 ≤ $2 × 10^7$。