← 返回题目列表

Codeforces · 1256/B

B. 最小化排列

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

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

您最多可以使用给定的排列执行 $$$n-1$$$ 操作(您可能根本不执行任何操作)。 $$$i$$$ 操作允许您在位置 $$$i$$$ 和 $$$i+1$$$ 上交换给定排列的元素。每个操作最多可以执行一次。这些操作可以按任意顺序执行。

您的任务是找到通过按某种顺序执行某些给定操作获得的按字典顺序排列的最小可能排列。

你可以在注释部分看到字典顺序的定义。

您必须回答 $$$q$$$ 独立测试用例。

例如,让我们考虑排列 $$$[5, 4, 1, 3, 2]$$$。我们可以获得的最小可能排列是 $$$[1, 5, 2, 4, 3]$$$,我们可以通过以下方式实现:

1.执行第二个操作(交换第二个和第三个元素),得到排列$$$[5, 1, 4, 3, 2]$$$;
2.执行第四个操作(交换第四个和第五个元素),得到排列$$$[5, 1, 4, 2, 3]$$$;
3. 执行第三次操作(交换第三个和第四个元素),得到排列$$$[5, 1, 2, 4, 3]$$$。
4. 执行第一个操作(交换第一个和第二个元素)并获得排列 $$$[1, 5, 2, 4, 3]$$$;

另一个例子是$$$[1, 2, 4, 3]$$$。通过执行第三个操作(交换第三个和第四个元素),我们可以获得的最小可能排列是 $$$[1, 2, 3, 4]$$$。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 测试用例的数量。然后是 $$$q$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 排列中的元素数量。

测试用例的第二行包含从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数 — 给定的排列。

输出

对于每个测试用例,在其上打印答案 - 通过按某种顺序执行某些给定操作获得的字典顺序最小可能排列。

示例

输入 #1

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

输出 #1

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

注意

回想一下,如果存在这样的索引 $$$i \le n$$$,对于从 $$$1$$$ 到 $$$i - 1$$$ 的所有 $$$j$$$ ,条件 $$$p_j = q_j$$$ 满足,$$$p_i < q_i$$$。例如:

- $$$p = [1, 3, 5, 2, 4]$$$ 小于 $$$q = [1, 3, 5, 4, 2]$$$ (这样 $$$i=4$$$ 存在,$$$p_i < q_i$$$ 且对于每个 $$$j < i$$$ 都成立 $$$p_j = q_j$$$),
- $$$p = [1, 2]$$$ 小于 $$$q = [2, 1]$$$ (这样 $$$i=1$$$ 存在,$$$p_i < q_i$$$ 且对于每个 $$$j < i$$$ 都包含 $$$p_j = q_j$$$)。