06765. USACO·最佳队形 未做

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

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

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

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

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

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

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

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

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

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

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

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

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

【样例解释】

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

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

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

• 测试点 5-8：$N\le 750$。

• 测试点 9-18：没有额外限制。

脚注：

我们知道，序列 $s$ 的字典序大于序列 $t$ 当且仅当以下条件之一成立：- 在 $s_i\ne t_i$ 的第一个位置 $i$ 处，有 $s_i>t_i$。

• 当不存在这样的 $i$ 时，$s$ 的长度大于 $t$。

【数据规模与约定】

• 测试点 2-4：$N\le 100$。

• 测试点 5-8：$N\le 750$。

• 测试点 9-18：没有额外限制。