[AGC001F] Wide Swap

给出一个元素集合为 $\{1,2,\dots,N\}$ $(1\leq N\leq 500,000)$ 的排列 $P$，当有 $i,j$ $(1\leq i<j\leq N)$ 满足 $j-i\geq K$ $(1\leq K\leq N-1)$ 且 $|P_{i}-P_{j}|=1$时，可以交换 $P_{i}$ 和 $P_{j}$。 求：可能排列中字典序最小的排列。 输入格式： $N$ $K$ $P_{1}$ $P_{2}$ $\dots$ $P_{N}$

[problemUrl]: https://atcoder.jp/contests/agc001/tasks/agc001_f 長さ $ N $ の、$ 1\ ～\ N $ をちょうど $ 1 $ つずつ含む数列 $ P_1\ ...\ P_N $ が与えられます。 あなたはこの数列に対し、以下のような操作を何度でも行えます。 - 整数 $ i,j\ (1\ ≦\ i\ <\ j\ ≦\ N) $ を選ぶ。 - $ P_i $ と $ P_j $ の値を入れ替える。 - ただしこのとき、$ j\ -\ i\ ≧\ K $ かつ $ |P_i\ -\ P_j|\ =\ 1 $ を満たしていなければならない。 このような操作によって作ることのできる数列のうち、辞書順最小のものを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ P_1 $ $ P_2 $ $ ... $ $ P_N $

問題文中の操作によって作ることのできる辞書順最小の数列を出力せよ。

4 2
4 2 3 1

2
1
4
3

5 1
5 4 3 2 1

1
2
3
4
5

8 3
4 5 7 8 3 1 2 6

1
2
6
7
5
3
4
8

### 制約 - $ 2≦N≦500,000 $ - $ 1≦K≦N-1 $ - $ P $ は $ 1,\ 2,\ ...,\ N $ の順列である。 ### Sample Explanation 1 以下のような手順で操作を行えば良いです。 - $ 4\ 2\ 3\ 1 $ - $ 4\ 1\ 3\ 2 $ - $ 3\ 1\ 4\ 2 $ - $ 2\ 1\ 4\ 3 $