[AGC001F] Wide Swap

题目描述

[problemUrl]: https://agc001.contest.atcoder.jp/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$ を満たしていなければならない。 このような操作によって作ることのできる数列のうち、辞書順最小のものを求めてください。

输入输出格式

输入格式

The input is given from Standard Input in the following format:  $N$ $K$ $P_1$ $P_2$ $...$ $P_N$ 

输出格式

Print the lexicographically smallest permutation that can be obtained.

输入输出样例

输入样例 #1

4 2
4 2 3 1

输出样例 #1

2
1
4
3

输入样例 #2

5 1
5 4 3 2 1

输出样例 #2

1
2
3
4
5

输入样例 #3

8 3
4 5 7 8 3 1 2 6

输出样例 #3

1
2
6
7
5
3
4
8

输入样例 #4

4 2
4 2 3 1

输出样例 #4

2
1
4
3

输入样例 #5

5 1
5 4 3 2 1

输出样例 #5

1
2
3
4
5

输入样例 #6

8 3
4 5 7 8 3 1 2 6

输出样例 #6

1
2
6
7
5
3
4
8

说明

### 制約 - $2≦N≦500,000$ - $1≦K≦N-1$ - $P$ は $1,\ 2,\ ...,\ N$ の順列である。 ### Problem Statement You are given a permutation $P_1\ ...\ P_N$ of the set { $1$ , $2$ , ..., $N$ }. You can apply the following operation to this permutation, any number of times (possibly zero): - Choose two indices $i,j\ (1\ ≦\ i\ <\ j\ ≦\ N)$ , such that $j\ -\ i\ ≧\ K$ and $|P_i\ -\ P_j|\ =\ 1$ . Then, swap the values of $P_i$ and $P_j$ . Among all permutations that can be obtained by applying this operation to the given permutation, find the lexicographically smallest one. ### Constraints - $2≦N≦500,000$ - $1≦K≦N-1$ - $P$ is a permutation of the set { $1$ , $2$ , ..., $N$ }. ### Sample Explanation 1 以下のような手順で操作を行えば良いです。 - $4\ 2\ 3\ 1$ - $4\ 1\ 3\ 2$ - $3\ 1\ 4\ 2$ - $2\ 1\ 4\ 3$ ### Sample Explanation 4 One possible way to obtain the lexicographically smallest permutation is shown below: - $4\ 2\ 3\ 1$ - $4\ 1\ 3\ 2$ - $3\ 1\ 4\ 2$ - $2\ 1\ 4\ 3$