P15030 [UOI 2021 II Stage] A 先生的魔法球

双倍经验：

A 先生在他的橱柜里发现了一串 $n$ 个魔法球。所有这些魔法球的颜色都 **互不相同**，为了方便起见，颜色用从 $1$ 到 $n$ 的整数编号。当然，A 先生的球的数量是偶数。 此外，A 先生有一个整型数组 $Q$，他将把球的颜色记录在其中。初始时数组 $Q$ 为空。 A 生计划执行 $\frac{n}{2}$ 次以下类型的操作：英雄选择序列中相邻的一对球，将它们从序列中移除，并将移除球对应的颜色添加到数组 $Q$ 的开头。被移除的球在数组 $Q$ 中的相对顺序与在初始序列中相同。从序列中删除元素后，序列的两部分会连接起来，形成一个新的序列。 例如，如果球的颜色序列为 $\left\{1,5,3,2,6,4\right\}$，可以先向数组 $Q$ 的开头添加元素对 $\left\{2,6\right\}$，然后添加元素对 $\left\{3,4\right\}$，最后添加元素对 $\left\{1,5\right\}$ —— 这样得到的数组 $Q$ 将为 $[1,5,3,4,2,6]$。 现在 A 先生很好奇，通过执行 $\frac{n}{2}$ 次操作，可以得到的最小的（按字典序）数组 $Q$ 是什么。回忆一下，字典序定义如下。假设有两个数组。找到第一个两个数组元素不同的位置。如果在该位置第一个数组的元素小于第二个数组的元素，则第一个数组字典序小于第二个数组；否则，第一个数组字典序大于第二个数组。例如，以下不等式成立：$[10, 3, 1] < [10, 4, 5]$, $[1, 1, 1] < [1, 2, 3]$, $[1, 2, 3] < [10, 10, 10]$。 请帮助 A 先生找到可能的最小数组 $Q$ 的前 $k$ 个元素。

第一行包含两个整数 $n$ 和 $k$ $(1 \le k \le n \le 10^6)$。保证 $n$ 是偶数。 第二行包含 $n$ 个 **互不相同** 的整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le n)$ —— 表示球序列的颜色。

输出 $k$ 个整数 $q_1, q_2, \dots, q_k$ —— 可能的最小数组 $Q$ 的前几个元素。

### 评分细则 - （8 分）： $n \le 10^5, k = 1$； - （5 分）： $n \le 10^5, k = 2$； - （19 分）： $n \le 14$； - （16 分）： $n \le 10^3$； - （10 分）： $n \le 10^5, k \le 20$； - （24 分）： $n \le 10^5$； - （18 分）： 无额外限制。 翻译由 DeepSeek V3 完成