分数: 900 点
问题陈述
给你一个排列 P of 1, 2, \cdots, N.
你可以划分 P 完全进入 K 非空连续子序列,如您所愿。
Maroon 将重新排列您创建的子序列并将它们连接起来以形成新的排列 Q。 在这里,他将按字典顺序最大化 Q.
你想要划分 P 以字典顺序最小化的方式 Q。查找 Q 在这种情况下。
约束
- 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)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \cdots P_N
输出
打印 您选择的 Q 当您最佳划分时 P.
示例输入 1
3 2 1 2 3
示例输出 1
2 3 1
你有两种划分方法 P: (1, 2),(3) 和 (1), (2, 3).
在前一种情况下,Maroon 会按顺序重新排列它们 (3), (1, 2) 得到 Q = (3, 1, 2).
在后一种情况下,Maroon 会按顺序重新排列它们 (2, 3), (1) 得到 Q = (2, 3, 1).
因此,您应该选择后者。
示例输入 2
4 3 4 3 1 2
示例输出 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
示例输出 3
10 5 8 2 7 6 19 4 11 17 13 14 16 18 3 1 9 12 20 15