atcoder#AGC059B. [AGC059B] Arrange Your Balls

[AGC059B] Arrange Your Balls

Score : 700700 points

Problem Statement

You have NN balls of colors C1,C2,,CNC_1, C_2, \ldots, C_N. Here, all colors are represented by an integer between 11 and NN inclusive. You want to arrange the balls on a circle. After you do that, you will count the number of pairs of colors (X,Y)(X, Y) such that X<YX < Y and there exist two adjacent balls of colors XX and YY.

Find an arrangement that minimizes the number of such pairs. If there are many such arrangements, find any of them.

For example, for balls of colors 1,1,2,31, 1, 2, 3, if we arrange them as 1,1,2,31, 1, 2, 3, we get 33 pairs: (1,2),(2,3),(1,3)(1, 2), (2, 3), (1, 3). If we arrange them as 1,2,1,31, 2, 1, 3, we get only 22 pairs: (1,2),(1,3)(1, 2), (1, 3).

Solve TT test cases for each input file.

Constraints

  • 1T51041 \le T \le 5 \cdot 10^4
  • 3N21053 \le N \le 2 \cdot 10^5
  • 1CiN1 \le C_i \le N
  • The sum of NN in one input file doesn't exceed 21052\cdot 10^5.
  • All values in the input are integers.

Input

Input is given from Standard Input in the following format:

TT

case1case_1

case2case_2

\vdots

caseTcase_T

Each case is in the following format:

NN

C1C_1 C2C_2 \ldots CNC_N

Output

For each test case, output your answer in the following format:

A1A_1 A2A_2 \ldots ANA_N

Here, AiA_i is the color of the ii-th ball (in clockwise order) on the circle in your arrangement.

(A1,A2,,AN)(A_1, A_2, \ldots, A_N) should be a permutation of (C1,C2,,CN)(C_1, C_2, \ldots, C_N), and the number of pairs of colors (X,Y)(X, Y) such that X<YX < Y and there exist two adjacent balls of colors XX and YY, should be minimized.

If multiple solutions exist, any of them will be accepted.

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