题目背景

双倍经验：https://www.luogu.com.cn/problem/AT_arc080_c

题目描述

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$ 的前几个元素。

6 6
1 5 3 2 6 4

1 2 5 3 6 4 

6 5
2 3 1 5 6 4

1 4 2 3 5 

提示

评分细则

• （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 完成