分数: 700 点
问题陈述
你有 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 每个输入文件的测试用例。 一个输入文件中的
约束
- 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.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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
1 2 3 2 1 3 1 3 3 2 5 2