← 返回题目列表

Codeforces · 2205/A

A. 西蒙斯和让它变得美丽

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

那些困扰我的麻烦——要么交出费用,要么就靠边站。
— 顺, 把它拿走

对于长度为 $$$m$$$ 的排列$$$^{\text{∗}}$$$ $$$r$$$,我们将索引称为 $$$i$$$ ($$$1\le i\le m$$$) 丑陋 当且仅当$$$i=\max(\{r_1,r_2,\ldots,r_i\})$$$。

Simons 有一个长度为 $$$n$$$ 的排列 $$$p$$$,他可以对 $$$p$$$ 执行以下操作 最多一次:

  • 选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1\le i\ne j\le n$$$),然后交换 $$$p_i$$$ 和 $$$p_j$$$。

通过最多执行一次上述操作,从$$$p$$$中找到一个排列$$$q$$$,使得 $$$q$$$ 中的 丑陋 指数被最小化。

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

输入

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

第一行包含一个整数 $$$n$$$ ($$$1\le n\le 500$$$) — $$$p$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1\le p_i\le n$$$,所有 $$$p_i$$$-s 都是不同的) — $$$p$$$ 的元素。

输出

对于每个测试用例,打印 $$$n$$$ 整数 $$$q_1,q_2,\ldots,q_n$$$ — 您找到的排列。

如果有多种可能的排列,您可以输出任何一种。

示例

输入
复制

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

输出
复制

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

注意

在第一个测试用例中,Simons 只能获得两种可能的排列:$$$[1,2]$$$ 和 $$$[2,1]$$$。

  • 对于排列 $$$[1,2]$$$,我们可以看到 $$$1=\max(\{1\})$$$ 和 $$$2=\max(\{1,2\})$$$。所以有两个 丑陋 指数。
  • 对于排列 $$$[2,1]$$$,我们可以看到 $$$1\ne\max(\{2\})$$$ 和 $$$2=\max(\{2,1\})$$$。所以只有一个 丑陋 索引。

因此,排列 $$$[2,1]$$$ 的最小计数为 丑陋 指数。

在第二个测试用例中,Simons 通过选择索引 $$$2$$$ 和 $$$4$$$ 进行交换,可以获得排列 $$$[2,4,1,3]$$$。只有一个 丑陋 排列中的索引:

  • $$$1\ne \max(\{2\})$$$,所以索引 $$$1$$$ 不是 丑陋;
  • $$$2\ne \max(\{2,4\})$$$,所以索引 $$$2$$$ 不是 丑陋;
  • $$$3\ne \max(\{2,4,1\})$$$,所以索引 $$$3$$$ 不是 丑陋;
  • $$$4=\max(\{2,4,1,3\})$$$,所以索引 $$$4$$$ 是 丑陋.

在第三个测试用例中,请注意 Simons 没有执行该操作。