题目描述

あなたは、色 $C_1,\ C_2,\ \ldots,\ C_N$ の $N$ 個のボールを持っています。 ここで、すべての色は $1$ 以上 $N$ 以下の整数により表されます。 あなたは、これらのボールを円周上に並べようとしています。その後、色のペア $(X,\ Y)$ であって、$X\ <\ Y$ であり、色 $X$ と $Y$ の二つの隣接するボールが存在するようなペアの個数を数えます。

そのようなペアの個数を最小化する配置を求めてください。そのような配置が多数存在する場合は、そのうちのいずれかを求めてください。

例えば、色 $1,\ 1,\ 2,\ 3$ のボールについて、$1,\ 1,\ 2,\ 3$ と並べると、$(1,\ 2),\ (2,\ 3),\ (1,\ 3)$ という $3$ つのペアが現れます。$1,\ 2,\ 1,\ 3$ と並べると、現れるペアは $(1,\ 2),\ (1,\ 3)$ の $2$ つのみです。

各入力ファイルについて、$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$ の二つの隣接するボールが存在するようなペアの個数が最小化されていなければならない。

複数の解が存在する場合は、そのいずれも認められる。

题目大意

$T$ 组数据，每次给定 $n$ 个球的颜色 $c_i$, $1\leq c_i$ , $c_i\leq n$，将球排成 $n$ 元环，最小化不同的无序二元组 $(a,b)$ 的数量，其中存在相邻两个球的颜色分别为 $a$ 和 $b$ ，且 $a\neq b$ 。输出任意一种满足条件的方案。

翻译者：蒟蒻君HJT

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\ \le\ T\ \le\ 5\ \cdot\ 10^4$
• $3\ \le\ N\ \le\ 2\ \cdot\ 10^5$
• $1\ \le\ C_i\ \le\ N$
• 各入力ファイル内の $N$ の総和は $2\cdot\ 10^5$ を超えない。
• 入力中のすべての値は整数である。