#1664. 「USACO 2025.2 Silver」The Best Lineup

Farmer John 有 （）头奶牛排成一条队伍 。队伍 中从前到后第 头奶牛编号为一个整数 （）。可能存在多头奶牛编号为同一整数。

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

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

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

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

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

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

每个测试点将包含 （）个独立的测试用例。

输入的第一行包含 。

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

每一个测试用例的第二行包含 个空格分隔的整数 。

输入保证所有测试用例的 之和不超过 。

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

输入 #1

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

输出 #1

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

样例 1 解释：

在第一个测试用例中，FJ 可以将第五头奶牛移动到第二头奶牛之后。现在，。可以证明， 也是字典序最大的 。

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

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

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

脚注

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

• 在 的第一个位置 处，有 。
• 当不存在这样的 时， 的长度大于 。