Sliding Window Sort 2

时间限制：2s
空间限制：1024MB

题目描述

给定一个由 $1$ 到 $N$ 的整数构成的排列 $P=(P_1,P_2,\ldots,P_N)$ 和一个整数 $K$。

你需要恰好进行一次如下操作：选择一个满足 $1\le i\le N-K+1$ 的整数 $i$，将 $P_i,P_{i+1},\ldots,P_{i+K-1}$ 按升序排列。

请输出所有可能得到的排列中字典序最大的一个。

对于两个长度相同的序列 $S,T$，若在第一个满足 $S_j\ne T_j$ 的位置 $j$ 上有 $S_j<T_j$，则称 $S$ 的字典序小于 $T$。

输入格式

第一行输入两个整数 $N,K$。

第二行输入 $N$ 个整数 $P_1,P_2,\ldots,P_N$。

输出格式

输出字典序最大的结果排列，相邻整数之间用一个空格分隔。

样例输入 1

4 3
2 1 4 3

样例输出 1

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

数据范围

对于所有数据，$1\le K\le N\le 2\times 10^5$，且 $P$ 是 $1$ 到 $N$ 的一个排列。