{"raw_statement":[{"iden":"problem statement","content":"You have $N$ balls of colors $C_1, C_2, \\ldots, C_N$. Here, all colors are represented by an integer between $1$ and $N$ 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)$ such that $X < Y$ and there exist two adjacent balls of colors $X$ and $Y$.\nFind an arrangement that minimizes the number of such pairs. If there are many such arrangements, find any of them.\nFor example, for balls of colors $1, 1, 2, 3$, if we arrange them as $1, 1, 2, 3$, we get $3$ pairs: $(1, 2), (2, 3), (1, 3)$. If we arrange them as $1, 2, 1, 3$, we get only $2$ pairs: $(1, 2), (1, 3)$.\nSolve $T$ test cases for each input file."},{"iden":"constraints","content":"*   $1 \\le T \\le 5 \\cdot 10^4$\n*   $3 \\le N \\le 2 \\cdot 10^5$\n*   $1 \\le C_i \\le N$\n*   The sum of $N$ in one input file doesn't exceed $2\\cdot 10^5$.\n*   All values in the input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is in the following format:\n\n$N$\n$C_1$ $C_2$ $\\ldots$ $C_N$"},{"iden":"sample input 1","content":"3\n3\n1 2 3\n4\n1 2 1 3\n5\n2 2 5 3 3"},{"iden":"sample output 1","content":"1 2 3 \n2 1 3 1 \n3 3 2 5 2"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}