题目描述

你有 $N$ 个颜色分别为 $C_1,\ C_2,\ \ldots,\ C_N$ 的球。这里，所有颜色都用 $1$ 到 $N$ 之间的整数表示。你打算将这些球沿圆周排列。之后，你需要统计所有满足 $X < Y$ 的颜色对 $(X, Y)$，使得存在一对相邻的球分别为颜色 $X$ 和 $Y$ 的这样的对的数量。

请你求出使得上述颜色对数量最小的排列方式。如果有多种排列方式，输出其中任意一种即可。

例如，对于颜色为 $1,\ 1,\ 2,\ 3$ 的球，如果排列为 $1,\ 1,\ 2,\ 3$，则会出现 $3$ 个颜色对：$(1, 2),\ (2, 3),\ (1, 3)$。如果排列为 $1,\ 2,\ 1,\ 3$，则只会出现 $2$ 个颜色对：$(1, 2),\ (1, 3)$。

对于每个输入文件，请解决 $T$ 个测试用例。

输入格式

输入由标准输入给出，格式如下：

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

每个测试用例如下格式：

$N\ C_1\ C_2\ \ldots\ C_N$

输出格式

对于每个测试用例，输出一行答案，格式如下：

$A_1\ A_2\ \ldots\ A_N$

其中，$A_i$ 表示圆周上（按顺时针方向）第 $i$ 个球的颜色。

$(A_1,\ A_2,\ \ldots,\ A_N)$ 必须是 $(C_1,\ C_2,\ \ldots,\ C_N)$ 的一个排列，并且颜色对 $(X, Y)$（$X < Y$ 且 $X$ 和 $Y$ 有相邻的球）出现的数量应当最小。

如果存在多个解，输出任意一个即可。

样例 1

输入

3
3
1 2 3
4
1 2 1 3
5
2 2 5 3 3

输出

1 2 3 
2 1 3 1 
3 3 2 5 2

说明/提示

限制

• $1 \leq T \leq 5 \cdot 10^4$
• $3 \leq N \leq 2 \cdot 10^5$
• $1 \leq C_i \leq N$
• 每个输入文件中所有 $N$ 的总和不超过 $2 \cdot 10^5$
• 输入中的所有值均为整数。

由 ChatGPT 4.1 翻译