/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
1, 2, \cdots, N の順列 P が与えられます．
あなたは好きなように P をちょうど K 個の非空な連続部分列に分割することができます．
maroon 君はあなたの分割した連続部分列を並び替え，連結して，新しく順列 Q を作ります．maroon 君は Q を辞書順で最大にしようとします．
あなたは Q が辞書順で最小になるように P を連続部分列に分割したいです．そのときの 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
出力
あなたが P を最適に分割した場合の Q を出力せよ．
入力例 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
Score : 900 points
Problem Statement
You are given a permutation P of 1, 2, \cdots, N.
You can divide P into exactly K non-empty contiguous subsequences as you like.
Maroon will rearrange those subsequences you make and concatenate them to make a new permutation Q. Here, he will lexicographically maximize Q.
You want to divide P in a way that lexicographically minimizes Q. Find Q in that case.
Constraints
- 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)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K P_1 P_2 \cdots P_N
Output
Print Q when you optimally divide P.
Sample Input 1
3 2 1 2 3
Sample Output 1
2 3 1
You have two ways to divide P: (1, 2),(3) and (1), (2, 3).
In the former case, Maroon will rearrange them in the order (3), (1, 2) to get Q = (3, 1, 2).
In the latter case, Maroon will rearrange them in the order (2, 3), (1) to get Q = (2, 3, 1).
Thus, you should choose the latter.
Sample Input 2
4 3 4 3 1 2
Sample Output 2
4 3 1 2
Sample Input 3
20 7 10 5 8 2 1 9 12 20 15 3 7 6 19 4 11 17 13 14 16 18
Sample Output 3
10 5 8 2 7 6 19 4 11 17 13 14 16 18 3 1 9 12 20 15