删除与旋转

题目描述

给定一个包含 $1,2,\ldots,N$ 各恰好一次的数列 $P = (p_1,p_2,\ldots,p_N)$。

你可以执行以下操作，总次数在 $0$ 到 $K$ 次之间，顺序任意：

• 选择 $P$ 中的一个元素并删除它。
• 将 $P$ 的最后一个元素移到开头。

求通过操作能得到的最小字典序的 $P$。

输入格式

输入按以下格式从标准输入给出：

$N$ $K$
$p_1$ $p_2$ $\ldots$ $p_N$

输出格式

输出操作后能得到的最小字典序的 $P$，以空格分隔。

样例

5 3
4 5 2 3 1

1 2 3

通过以下操作可以使 $P$ 变为 $(1,2,3)$：

• 删除第一个元素，$P$ 变为 $(5,2,3,1)$。
• 将最后一个元素移到开头，$P$ 变为 $(1,5,2,3)$。
• 删除第二个元素，$P$ 变为 $(1,2,3)$。

不存在字典序比 $(1,2,3)$ 更小的 $P$，所以这就是答案。

3 0
3 2 1

3 2 1

也可以不执行任何操作。

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

1 3 4 7 2 8 11 9

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le K \le N-1$
• $1 \le p_i \le N$
• $(p_1,p_2,\ldots,p_N)$ 包含 $1,2,\ldots,N$ 各恰好一次。
• 输入均为整数