/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N までの整数からなる順列 P=(P_1,P_2,\dots,P_N) と整数 K が与えられます。
順列 P に対して以下のような操作を考えます。
- 1 \leq i \leq N-K+1 を満たす整数 i を 1 つ選び、 P_i,P_{i+1},\dots,P_{i+K-1} を昇順に並び替える。すなわち、P_i,P_{i+1},\dots,P_{i+K-1} を小さい方から順に並べたものを (x_1,x_2,\dots,x_K) としたとき、各 1 \leq j \leq K に対して P_{i+j-1} を x_j で置き換える。
P に対して上記の操作をちょうど 1 回行うことで得られる順列のうち、辞書式順序最大のものを求めてください。
数列の辞書順とは？
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|S|, |T| はそれぞれ S, T の長さを表します。
- |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq N
- (P_1,P_2,\dots,P_N) は 1 から N までの整数からなる順列
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K P_1 P_2 \dots P_N
出力
P に対して操作をちょうど 1 回行うことで得られる順列のうち、辞書式順序で最大のものを空白区切りで出力してください。
入力例 1
4 3 2 1 4 3
出力例 1
2 1 3 4
i=1 として操作を行うと (P_1,P_2,P_3)=(2,1,4) であり、これを昇順に並び替えると (1,2,4) となります。よって操作によって P_1,P_2,P_3 はそれぞれ 1,2,4 に置き換えられ、 P=(1,2,4,3) となります。同様に i=2 として操作を行うと P は (2,1,3,4) となります。
これらのうち辞書式順序で大きいのは (2,1,3,4) であるため、答えは (2,1,3,4) となります。
入力例 2
5 1 3 1 4 2 5
出力例 2
3 1 4 2 5
入力例 3
20 7 9 4 3 1 11 12 13 15 17 7 2 5 6 20 19 18 8 16 14 10
出力例 3
9 4 3 1 11 12 13 15 17 7 2 5 6 8 18 19 20 16 14 10
Score : 600 points
Problem Statement
You are given a permutation P=(P_1,P_2,\dots,P_N) of integers from 1 to N and an integer K.
Consider the following operation on the permutation P.
- Choose an integer i such that 1 \leq i \leq N-K+1, and sort P_i,P_{i+1},\dots,P_{i+K-1} in ascending order. That is, let (x_1,x_2,\dots,x_K) be the result of arranging P_i,P_{i+1},\dots,P_{i+K-1} in order from smallest to largest, and replace P_{i+j-1} with x_j for each 1 \leq j \leq K.
Find the lexicographically largest permutation that can be obtained by performing the above operation on P exactly once.
What is lexicographical order on sequences?
A sequence S = (S_1,S_2,\ldots,S_{|S|}) is lexicographically smaller than T = (T_1,T_2,\ldots,T_{|T|}) when 1. or 2. below holds. Here, |S| and |T| denotes the lengths of S and T, respectively.
- |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace that satisfy both of the following:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i is smaller than T_i (as a number).
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq N
- (P_1,P_2,\dots,P_N) is a permutation of integers from 1 to N.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K P_1 P_2 \dots P_N
Output
Print the lexicographically largest permutation that can be obtained by performing the above operation on P exactly once, with spaces in between.
Sample Input 1
4 3 2 1 4 3
Sample Output 1
2 1 3 4
If you perform the operation with i=1, we have (P_1,P_2,P_3)=(2,1,4), and sorting it in ascending order yields (1,2,4). Thus, the operation replaces P_1,P_2,P_3 with 1,2,4, respectively, resulting in P=(1,2,4,3). Similarly, if you perform the operation with i=2, P becomes (2,1,3,4).
The lexicographically greater between them is (2,1,3,4), so the answer is (2,1,3,4).
Sample Input 2
5 1 3 1 4 2 5
Sample Output 2
3 1 4 2 5
Sample Input 3
20 7 9 4 3 1 11 12 13 15 17 7 2 5 6 20 19 18 8 16 14 10
Sample Output 3
9 4 3 1 11 12 13 15 17 7 2 5 6 8 18 19 20 16 14 10