P11839 [USACO25FEB] The Best Lineup S

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$。

样例 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$。