AT_abc262_f [ABC262F] Erase and Rotate

题目描述

给定一个只包含 $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$，用空格分隔。

输入输出样例 #1

输入 #1

5 3
4 5 2 3 1

输出 #1

1 2 3

输入输出样例 #2

输入 #2

3 0
3 2 1

输出 #2

3 2 1

输入输出样例 #3

输入 #3

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

输出 #3

1 3 4 7 2 8 11 9

说明/提示

限制条件

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

样例解释 1

可以按如下方式操作使 $P$ 变为 $(1,2,3)$：

• 删除首项，此时 $P$ 变为 $(5,2,3,1)$。
• 将末尾元素移到开头，此时 $P$ 变为 $(1,5,2,3)$。
• 删除从头数第 $2$ 个元素，此时 $P$ 变为 $(1,2,3)$。 并且，操作后无法得到字典序比 $(1,2,3)$ 更小的数列，因此这就是答案。

样例解释 2

有时你可能一次操作都无法进行。

由 ChatGPT 4.1 翻译