← 返回题目列表

Codeforces · 2101/B

B. 四重奏交换

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

给你一个长度为 $$$n$$$$$^{\text{*}}$$$ 的排列 $$$a$$$。您可以执行以下操作任意次数(可能为零):

  • 选择索引 $$$1\le i\le n - 3$$$。然后,同时将 $$$a_i$$$ 与 $$$a_{i + 2}$$$ 交换,并将 $$$a_{i + 1}$$$ 与 $$$a_{i + 3}$$$ 交换。换句话说,排列 $$$a$$$ 将从 $$$[\ldots, a_i, a_{i+1}, a_{i+2}, a_{i+3}, \ldots]$$$ 转换为 $$$[\ldots, a_{i+2}, a_{i+3}, a_{i}, a_{i+1}, \ldots]$$$。

确定按字典顺序排列的最小排列$$$^{\text{†}}$$$,可以通过应用上述操作任意次来获得。

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

$$$^{\text{†}}$$$当且仅当以下条件成立时,数组 $$$x$$$ 按字典顺序小于相同大小的数组 $$$y$$$:

  • 在 $$$x$$$ 和 $$$y$$$ 不同的第一个位置,数组 $$$x$$$ 的元素比 $$$y$$$ 中的相应元素小。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4\le n\le 2\cdot 10^5$$$) — 排列 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 排列 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出通过应用上述操作任意次数可以获得的字典顺序最小排列。

示例

输入
复制

3
4
3 4 1 2
5
5 4 3 1 2
10
10 9 8 7 6 5 4 3 2 1

输出
复制

1 2 3 4 
2 1 3 4 5 
2 1 4 3 6 5 8 7 10 9 

注意

在第一个测试用例中,可以对索引 $$$i = 1$$$ 进行操作,排列将变为 $$$[1, 2, 3, 4]$$$,这是按字典顺序可实现的最小排列。

在第二个测试用例中,我们可以执行以下操作序列:

  • 对索引 $$$i = 2$$$ 执行操作。排列变为 $$$[5, 1, 2, 4, 3]$$$。
  • 对索引 $$$i = 1$$$ 执行操作。排列变为 $$$[2, 4, 5, 1, 3]$$$。
  • 对索引 $$$i = 2$$$ 执行操作。排列变为 $$$[2, 1, 3, 4, 5]$$$。