← 返回题目列表

AtCoder · agc059_b

B. 安排你的球

中文机器翻译题面 查看原题

分数: 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