CF2205A Simons and Making It Beautiful

那些紧紧跟随我的麻烦——要么付出代价，要么让路。 —— SHUN, [TAKE IT AWAY](https://open.spotify.com/track/4hpmSSMqgesMBCc3GNopCF) 对于一个长度为 $m$ 的排列 $r$，如果某个下标 $i$（$1 \le i \le m$）满足 $i = \max(\{r_1, r_2, \ldots, r_i\})$，我们称下标 $i$ 是丑陋下标。 Simons 有一个长度为 $n$ 的排列 $p$，他最多可以对 $p$ 执行以下操作一次： - 选择两个不同的下标 $i$ 和 $j$（$1 \le i \ne j \le n$），交换 $p_i$ 和 $p_j$。 请你找出一个可以通过至多执行一次上述操作从 $p$ 得到的排列 $q$，使得 $q$ 中丑陋下标的数量最少。 一个长度为 $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$ 互不相同），表示排列 $p$ 的元素。

对于每组测试用例，输出 $n$ 个整数 $q_1, q_2, \ldots, q_n$，表示你找到的满足要求的排列。 如果存在多种可能的排列，你可以输出任意一种。

在第一个测试用例中，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 没有进行任何操作。 由 ChatGPT 5 翻译