题目描述

那些紧紧跟随我的麻烦——要么付出代价，要么让路。

—— SHUN, TAKE IT AWAY

对于一个长度为 $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 翻译

样例

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