CF2156F1.Strange Operation (Easy Version)

这是本题的简单版本。本版本与其他版本的区别在于 $n$ 的限制更小。只有完成了所有版本的题目，你才能 hack 本题。

给定一个长度为 $n$ 的排列 $p$。你可以进行如下操作任意次（也可以不做）：

• 选择三个互不相同的下标 $i$，$j$，$k$，满足 $1 \le i < j < k \le n$，并且同时满足以下两个条件：$p_i = \max(p_j, p_k) + 1$ 并且 $p_i = \min(p_j, p_k) + 2$。然后，将 $p_i$ 减去 $2$，$p_j$ 和 $p_k$ 都加上 $1$。形式化地，$p_i := p_i - 2$，$p_j := p_j + 1$，$p_k := p_k + 1$。

可以证明，通过上述操作后 $p$ 仍然是一个排列，因为满足 $p_i = \max(p_j, p_k) + 1$ 和 $p_i = \min(p_j, p_k) + 2$ 两个条件。

你的任务是，在任意次操作后，求出可以得到的字典序最小的排列。

$^{\text{∗}}$ 长度为 $n$ 的排列是由 $1$ 到 $n$ 的所有整数按任意顺序排列而成的数组。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但有 $4$ 出现）。

$^{\text{†}}$ 若有两个长度相等的序列 $a$ 和 $b$，若 $a \ne b$ 且在第一个不同的位置，$a$ 对应的元素小于 $b$ 对应的元素，则称 $a$ 的字典序小于 $b$。

每组测试数据可能包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。

每组测试用例的第一行包含一个整数 $n$（$3 \le n \le 2000$），表示排列 $p$ 的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$），表示排列 $p$ 的元素。

保证所有测试用例的 $n^2$ 之和不超过 $2000^2$。

对于每组测试用例，输出 $n$ 个整数，表示在任意次操作后能够得到的字典序最小的排列。

在第一组样例中，最优策略是对 $i=1$，$j=2$，$k=3$ 进行一次操作。注意不能选择 $i=1$，$j=3$，$k=4$，因为这虽然满足第二个条件 $p_1 = \min(p_3, p_4) + 2$，但第一个条件 $p_1 = \max(p_3, p_4) + 1$ 不满足。

在第二组样例中，可以按如下顺序操作：

• 选择 $i=1$，$j=4$，$k=5$，此时排列变为 $[1, 4, 5, 3, 2]$。
• 选择 $i=2$，$j=4$，$k=5$，此时排列变为 $[1, 2, 5, 4, 3]$。
• 选择 $i=3$，$j=4$，$k=5$，此时排列变为 $[1, 2, 3, 5, 4]$。

在第三组样例中，没有 $i < j < k$ 的三元组同时满足上面的条件，因此无法操作。

由 ChatGPT 5 翻译