首先考虑求出原排列的逆置换，设为 $Q$ ，于是交换就变成了如果 $|Q_i - Q_{i+1}| < k$ 那么可以交换相邻的两个元素。

于是，对于任意 $i,j$ 如果满足 $|Q_i - Q_j| < k$ 那么他们的相对顺序一定无法改变。

而且可以证明，如果两个排列 $Q,P$ 中所有元素的相对位置的关系是一样的，那么一定可以从 $Q$ 移到 $P$ 。考虑这种情况下的一次移动就可以让逆序减少 $1$ 。有限步的操作后一定可以让 $Q$ 成为 $P$ （画一下发现很对）。

于是有了一种做法，对于 $i<j$ 满足 $|Q_i - Q_j| < k$ 我们连一条 $Q_i \to Q_j$ 的有向边表示先 $Q_i$ 后 $Q_j$ ，于是我们要求的就是这个图上的一个拓扑序，满足 $1$ 尽量靠前，在 $1$ 尽量靠前的情况下 $2$ 尽量靠前… 不难发现这样的限制等价于原排列字典序尽量小。这个限制与字典序是没有关系的。比如 $3 \to 1 , 2 \to 4$ 在这个限制下应该拿 $3,1,2,4$ 但是字典序最小的应当是 $2,3,1,4$ 。

求这个拓扑序的方法可以参照 LOJ2114 这个题。我们每次拿可以放在最后的最大的数放在最后一定不劣。所以我们可以建反图再跑拓扑序，最后把拓扑序倒过来就得到了所求。

现在问题在于这样的边有 $O(n^2)$ 条。优化方法大致有两种。首先可以不建边，直接在线段树上判断一个点的出度来做拓扑排序，这是官方题解的做法。大概还有一个做法是优化边的数量。

考虑我们当前已经通过加边让 $1 \sim i - 1$ 的点对间都满足了之前提到的限制。现在我们加入 $Q_i$ 。我们只给满足 $0< Q_j - Q_i < k$ 以及 $0 < Q_i - Q_j < k$ 且大的两个 $j$ 与 $Q_i$ 连边。由于上下是对称的，我们只考虑 $Q_j > Q_i$ 的情况。因为之前 $1 \sim i - 1$ 中与 $i$ 满足 $Q_t -Q_i < k$ 的位置 与 $Q_j$ 的相对顺序已经是确定好的，并且一定是 $Q_j$ 处于最靠后，所以直接拿 $Q_j$ 向 $Q_i$ 连边即可满足所有的限制。这样连边最多也就连 $2n$ 条，边数变成了 $O(n)$ 级别。连边过程用线段树维护，总复杂度是连边的 $O(n\log n)$。

最后别忘了要还原成原排列。。这毒瘤样例全部不还原都能过

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , k;
int A[MAXN] , Q[MAXN];

int T[MAXN << 2];
void add( int rt , int l , int r , int x , int c ) {
	if( l == r ) { T[rt] = c; return; }
	int m = l + r >> 1;
	if( x <= m ) add( rt << 1 , l , m , x , c );
	else add( rt << 1 | 1 , m + 1 , r , x , c );
	T[rt] = max( T[rt << 1] , T[rt << 1 | 1] );
}
int que( int rt , int l , int r , int L , int R ) {
	if( L <= l && R >= r ) return T[rt];
	int m = l + r >> 1 , re = 0;
	if( L <= m ) re = max( re , que( rt << 1 , l , m , L , R ) );
	if( R > m ) re = max( re , que( rt << 1 | 1 , m + 1 , r , L , R ) );
	return re;
}

vi G[MAXN];
int deg[MAXN] , as[MAXN];

void solve() {
	cin >> n >> k;
	rep( i , 1 , n ) scanf("%d",A + i) , Q[A[i]] = i;
	rep( i , 1 , n ) {
		int t = que( 1 , 1 , n , Q[i] , min( Q[i] + k - 1 , n ) );
		if( t ) G[Q[i]].pb( Q[t] ) , ++ deg[Q[t]];// , cout << Q[i] << ' ' << Q[t] << endl;
		t = que( 1 , 1 , n , max( 1 , Q[i] - k + 1 ) , Q[i] );
		if( t ) G[Q[i]].pb( Q[t] ) , ++ deg[Q[t]];// , cout << Q[i] << ' ' << Q[t] << endl;
		add( 1 , 1 , n , Q[i] , i );
	}
	priority_queue<int> q;
	rep( i , 1 , n ) if( !deg[i] ) q.push( i );
	vi re;
	while( !q.empty() ) {
		int u = q.top(); q.pop();
		for( int v : G[u] ) {
			-- deg[v];
			if( !deg[v] ) q.push( v );
		}
		re.pb( u );
	}
	reverse( all( re ) );
	rep( i , 1 , n ) as[re[i - 1]] = i;
	rep( i , 1 , n ) printf("%d\n",as[i]);
}

signed main() {
//	freopen("input","r",stdin);
//	freopen("stdout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}