题目描述

给定一个 $1, 2, \cdots, N$ 的排列 $P$。

你可以将 $P$ 恰好分割成 $K$ 个非空的连续子序列，方式任意。

maroon 君会将你分割出的连续子序列重新排列并连接起来，得到一个新的排列 $Q$。maroon 君会选择使 $Q$ 字典序最大的排列方式。

你希望 $Q$ 的字典序尽可能小。请输出你在最优分割下得到的 $Q$。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $P_1$ $P_2$ $\cdots$ $P_N$

输出格式

请输出你最优分割下得到的 $Q$。

样例 1

输入

3 2
1 2 3

输出

2 3 1

样例 2

输入

4 3
4 3 1 2

输出

4 3 1 2

样例 3

输入

20 7
10 5 8 2 1 9 12 20 15 3 7 6 19 4 11 17 13 14 16 18

输出

10 5 8 2 7 6 19 4 11 17 13 14 16 18 3 1 9 12 20 15

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq N$
• $1 \leq P_i \leq N$
• $P_i \neq P_j\ (i \neq j)$
• 输入均为整数

样例解释 1

对于 $P$ 的分割方式，可以是 $(1, 2), (3)$ 或 $(1), (2, 3)$。
前者情况下，maroon 君会将 $(3), (1, 2)$ 重新排列，得到 $Q = (3, 1, 2)$。
后者情况下，maroon 君会将 $(2, 3), (1)$ 重新排列，得到 $Q = (2, 3, 1)$。
因此，你应该选择后者的分割方式。

由 ChatGPT 4.1 翻译