对于长度为 $$$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$$$ — 您找到的排列。
如果有多种可能的排列,您可以输出任何一种。
示例
输入复制
521 242 3 1 453 2 4 5 11184 1 3 2 6 7 8 5
输出复制
2 12 4 1 33 2 4 5 114 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 没有执行该操作。