题目描述

Farmer John 有 $N$（$1 \leq N \leq 2 \cdot 10^5$）头奶牛排成一条队伍 $a$。队伍 $a$ 中从前到后第 $i$ 头奶牛编号为一个整数 $a_i$（$1 \leq a_i \leq N$）。可能存在多头奶牛编号为同一整数。

FJ 将以以下方式构造另一条队伍 $b$：

• 初始时，$b$ 为空。
• 当 $a$ 非空时，移除 $a$ 最前面的奶牛，并选择是否将该奶牛添加到 $b$ 的最后。

FJ 想要构造队伍 $b$，使得 $b$ 中从前到后的编号序列是字典序最大的（见脚注）。

在 FJ 构造队伍 $b$ 之前，他可以执行以下操作至多一次：

• 选择队伍 $a$ 中的一头奶牛，并将其移动至当前位置之前的任意位置。

假设 FJ 以最优方式执行至多一次上述操作，输出他可以达到的字典序最大的 $b$ 的编号序列。

每个测试点将包含 $T$（$1 \leq T \leq 100$）个独立的测试用例。

输入格式

输入的第一行包含 $T$。

每一个测试用例的第一行包含 $N$。

每一个测试用例的第二行包含 $N$ 个空格分隔的整数 $a_1, a_2, \ldots, a_N$。

输入保证所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

对于每一个测试用例输出一行，包含字典序最大的 $b$。

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

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

提示

样例 1 解释：

在第一个测试用例中，FJ 可以将第五头奶牛移动到第二头奶牛之后。现在，$a = [4, 3, 3, 2, 1]$。可以证明，$[4, 3, 3, 2, 1]$ 也是字典序最大的 $b$。

在第二个测试用例中，FJ 可以将第四头奶牛移动到队伍的最前面。

在第三个测试用例中，FJ 不需要执行任何操作。他可以通过将除第二头奶牛之外的每头奶牛添加到 $b$ 的最后来构造 $b$。可以证明，这得到了字典序最大的 $b$。

• 测试点 $2\sim 4$：$N \leq 100$。
• 测试点 $5\sim 8$：$N \leq 750$。
• 测试点 $9\sim 18$：没有额外限制。

脚注

我们知道，序列 $s$ 的字典序大于序列 $t$ 当且仅当以下条件之一成立：

• 在 $s_i \neq t_i$ 的第一个位置 $i$ 处，有 $s_i > t_i$。
• 当不存在这样的 $i$ 时，$s$ 的长度大于 $t$。