← 返回题目列表

AtCoder · arc114_f

F. 排列除法

中文机器翻译题面 查看原题

分数: 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