题目描述

我们称长度为 $2n$ 的整数序列 $X=(X_1,X_2,\dots,X_{2n})$，如果对于所有 $i=1,2,\dots,n$ 都满足 $X_{2i-1}=X_{2i}$，则称 $X$ 为良好数列。

给定一个长度为 $2N$ 的整数序列 $A=(A_1,A_2,\dots,A_{2N})$。该序列包含每个整数 $i=1,2,\dots,N$ 恰好各 $2$ 个。

你可以对 $A$ 进行若干次“交换相邻的两个元素”的操作（可以为 $0$ 次），希望将 $A$ 变为良好数列。

设将 $A$ 变为良好数列所需的最小操作次数为 $K$。请你输出对 $A$ 进行 $K$ 次操作后，能够得到的良好数列中字典序最小的一个，元素之间用空格分隔。

数列的字典序定义如下：设 $S=(S_1,S_2,\ldots,S_{|S|})$，$T=(T_1,T_2,\ldots,T_{|T|})$，则 $S$ 的字典序小于 $T$ 当且仅当满足以下两条之一。这里 $|S|,|T|$ 分别表示 $S,T$ 的长度。

1. $|S|<|T|$ 且 $(S_1,S_2,\ldots,S_{|S|})=(T_1,T_2,\ldots,T_{|S|})$。
2. 存在整数 $1\leq i\leq \min\lbrace |S|,|T| \rbrace$，使得同时满足：
   • $(S_1,S_2,\ldots,S_{i-1})=(T_1,T_2,\ldots,T_{i-1})$；
   • $S_i$ 比 $T_i$ 小（按数值比较）。

输入格式

输入以以下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\dots$ $A_{2N}$

输出格式

请输出对 $A$ 进行 $K$ 次操作后能够得到的良好数列中字典序最小的一个，元素之间用空格分隔。

样例 1

输入

3
3 2 1 2 3 1

输出

2 2 3 3 1 1

样例 2

输入

3
1 1 2 2 3 3

输出

1 1 2 2 3 3

样例 3

输入

15
15 12 11 10 5 11 13 2 6 14 3 6 5 14 10 15 1 2 13 9 7 4 9 1 3 8 12 4 8 7

输出

11 11 5 5 6 6 10 10 14 14 15 15 2 2 12 12 13 13 1 1 3 3 9 9 4 4 7 7 8 8

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $1\leq A_i\leq N$
• 每个整数 $i=1,2,\dots,N$ 在 $A$ 中恰好出现 $2$ 次
• 输入的所有值均为整数

样例解释 1

例如，$(3,2,1,2,3,1)\rightarrow (3,2,1,3,2,1)\rightarrow (3,2,3,1,2,1)\rightarrow (3,3,2,1,2,1)\rightarrow (3,3,2,2,1,1)$，这样经过 $4$ 次操作可以将 $A$ 变为良好数列，这是所需的最小操作次数。在 $4$ 次操作下，也可以得到 $A=(2,2,3,3,1,1)$，因此答案为 $(2,2,3,3,1,1)$。

由 ChatGPT 4.1 翻译