给你一个长度为 $$$n$$$ 的排列 $$$p$$$。
排列是由 $$$n$$$ 不同的整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 可以任意顺序。例如,$$$\{2,3,1,5,4\}$$$ 是排列,而 $$$\{1,2,2\}$$$ 不是排列(因为 $$$2$$$ 出现了两次),$$$\{1,3,4\}$$$ 也不是排列(因为 $$$n=3$$$,但数组包含 $$$4$$$)。
对于排列$$$p$$$,您需要应用以下操作一次:
- 首先选择一个段$$$[l, r]$$$($$$1 \le l \le r \le n$$$,一个段是一个连续的数字序列$$$\{p_l, p_{l+1}, \ldots, p_{r-1}, p_r\}$$$)并将其反转。反转段意味着交换数字对 $$$(p_l, p_r)$$$, $$$(p_{l+1}, p_{r-1})$$$, ..., $$$(p_{l + i}, p_{r - i})$$$ (其中 $$$l + i \le r - i$$$)。
- 然后交换前缀和后缀:$$$[r+1, n]$$$ 和 $$$[1, l - 1]$$$ (请注意,这些段可能为空)。
例如,给定 $$$n = 5, p = \{2, \color{blue}{3}, \color{blue}{1}, 5, 4\}$$$,如果您选择段 $$$[l = 2, r = 3]$$$,在反转段 $$$p = \{\color{green}{2}, \color{blue}{1}, \color{blue}{3} 后, \color{green}{5}, \color{green}{4}\}$$$,然后交换段 $$$[4, 5]$$$ 和 $$$[1, 1]$$$。因此,$$$p = \{\color{green}{5}, \color{green}{4}, 1, 3, \color{green}{2}\}$$$。可以证明这是给定排列的最大可能结果。
您需要输出按字典顺序排列的最大排列,该排列可以通过应用一次所描述的操作来获得。
如果存在 $$$i$$$ ($$$1 \le i \le n$$$) 使得 $$$a_j = b_j$$$ 对于 $$$1 \le j < i$$$ 且 $$$a_i > b_i$$$,则排列 $$$a$$$ 按字典顺序大于排列 $$$b$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
然后是测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — 排列的大小。
每个测试用例的第二行包含 $$$n$$$ 整数:$$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$ 本身。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
输出
对于每个测试用例,在单独的行中输出长度 $$$n$$$ 的字典顺序最大排列,该排列可以通过应用问题中描述的操作一次从 $$$p$$$ 获得。
示例
输入 #1
9 5 2 3 1 5 4 9 4 1 6 7 2 8 5 3 9 4 4 3 2 1 2 2 1 6 3 2 4 1 5 6 7 3 2 1 5 7 6 4 10 10 2 5 6 1 9 3 8 4 7 4 4 2 1 3 1 1
输出 #1
5 4 1 3 2 9 4 1 6 7 2 8 5 3 3 2 1 4 1 2 6 5 3 2 4 1 7 6 4 5 3 2 1 9 3 8 4 7 1 10 2 5 6 3 4 2 1 1
注意
第一个示例在问题陈述中进行了解释。
在第二个示例中,应选择段 $$$[l = 9, r = 9]$$$。
在第三个示例中,应选择段 $$$[l = 1, r = 1]$$$。
在第四个示例中,应选择段$$$[l = 1, r = 2]$$$。
在第五个示例中,应选择段$$$[l = 5, r = 6]$$$。
在第六个示例中,应选择段$$$[l = 4, r = 4]$$$。
在第七个示例中,应选择段$$$[l = 5, r = 5]$$$。