AT_arc165_f.[ARC165F] Make Adjacent

我们称长度为 $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\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 翻译