← 返回题目列表

Codeforces · 1638/A

A. 反向

中文机器翻译题面 查看原题

给你一个长度为 $$$n$$$ 的排列 $$$p_1, p_2, \ldots, p_n$$$。您必须选择两个整数 $$$l,r$$$ ($$$1 \le l \le r \le n$$$) 并反转排列的子段 $$$[l,r]$$$。排列将变为 $$$p_1,p_2, \dots, p_{l-1},p_r,p_{r-1}, \dots, p_l,p_{r+1},p_{r+2}, \dots ,p_n$$$。

找到按字典顺序排列的最小排列,该排列可以通过对初始排列执行一次反向操作来获得。

请注意,对于长度相等的两个不同排列 $$$a$$$ 和 $$$b$$$,$$$a$$$ 按字典顺序小于 $$$b$$$ 如果在第一个位置它们不同,则 $$$a$$$ 具有较小的元素。

排列是由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成的数组,按任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 排列的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列的元素。

输出

对于每个测试用例,打印您可以获得的按字典顺序排列的最小排列。

示例

输入 #1

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

输出 #1

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

注意

在第一个测试用例中,排列的长度为 $$$1$$$,因此唯一可能的段是 $$$[1,1]$$$。生成的排列是 $$$[1]$$$。

在第二个测试用例中,我们可以通过反转$$$[1,2]$$$段来获得恒等排列。生成的排列是 $$$[1,2,3]$$$。

在第三个测试用例中,最佳可能的段是 $$$[2,3]$$$。生成的排列是 $$$[1,2,4,3]$$$。

在第四个测试用例中,没有字典顺序更小的排列,因此我们可以通过选择段 $$$[1,1]$$$ 来保持它不变。生成的排列为 $$$[1,2,3,4,5]$$$。