AT_agc059_b [AGC059B] Arrange Your Balls

你有 $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 \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 翻译