CF2205A.Simons and Making It Beautiful

Those cling-on troubles that ride my stride — cough up the fee, or step aside.

— SHUN, TAKE IT AWAY

For a permutation$^{\text{∗}}$ $r$ of length $m$, we call an index $i$ ($1\le i\le m$) ugly if and only if $i=\max({r_1,r_2,\ldots,r_i})$.

Simons has a permutation $p$ of length $n$, and he can perform the following operation on $p$ at most once:

• Choose two indices $i$ and $j$ ($1\le i\ne j\le n$), then swap $p_i$ and $p_j$.

Find a permutation $q$ that can be obtained from $p$ by performing the above operation at most once, such that the number of ugly indices in $q$ is minimized.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

那些如影随形的烦扰——交出费用，抑或退避三舍。

— SHUN，《TAKE IT AWAY》（点击收听）

对于一个长度为 $m$ 的排列$^{\text{∗}}$ $r$，我们称下标 $i$（$1\le i\le m$）是“丑陋的”（ugly），当且仅当 $i=\max({r_1,r_2,\ldots,r_i})$。

西蒙斯拥有一个长度为 $n$ 的排列 $p$，他最多可对 $p$ 执行如下一次操作：

• 选择两个下标 $i$ 和 $j$（$1\le i\ne j\le n$），然后交换 $p_i$ 与 $p_j$。

请找出一个排列 $q$，它可通过至多执行上述一次操作由 $p$ 得到，使得 $q$ 中丑陋下标的个数最小。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数组成、顺序任意的数组。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中却出现了 $4$）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line contains an integer $n$ ($1\le n\le 500$) — the length of $p$.

The second line contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, all $p_i$-s are distinct) — the elements of $p$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 互不相同）—— 表示排列 $p$ 的元素。

For each test case, print $n$ integers $q_1,q_2,\ldots,q_n$ — the permutation you found.

If there are multiple possible permutations, you may output any.

对于每个测试用例，输出 $n$ 个整数 $q_1,q_2,\ldots,q_n$ —— 即你找到的排列。

如果存在多个可能的排列，你可以输出其中任意一个。

In the first test case, Simons can obtain only two possible permutations: $[1,2]$ and $[2,1]$.

• For permutation $[1,2]$, we can see $1=\max({1})$ and $2=\max({1,2})$. So there are two ugly indices.
• For permutation $[2,1]$, we can see $1\ne\max({2})$ and $2=\max({2,1})$. So there is only one ugly index.

Thus, permutation $[2,1]$ has the minimum count of ugly indices.

In the second test case, Simons can obtain permutation $[2,4,1,3]$ by choosing indices $2$ and $4$ to swap. There is only one ugly index in the permutation:

• $1\ne \max({2})$, so index $1$ is not ugly;
• $2\ne \max({2,4})$, so index $2$ is not ugly;
• $3\ne \max({2,4,1})$, so index $3$ is not ugly;
• $4=\max({2,4,1,3})$, so index $4$ is ugly.

In the third test case, note that Simons does not perform the operation.

在第一个测试用例中，西蒙斯只能得到两种可能的排列：$[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]$ 拥有最少的丑陋下标数量。

在第二个测试用例中，西蒙斯可通过选择下标 $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$ 是丑陋下标。

在第三个测试用例中，请注意西蒙斯不执行任何操作。