O(N logN)

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

void ckmin(int& a, int b) { a = min(a,b); }
void ckmax(int& a, int b) { a = max(a,b); }

mt19937 rng;
using pt = struct tnode*;

struct tnode {
	int mn, mx, val; // subtree min, subtree max, value at current node
	pt c[2];
	uint32_t pri{rng()};
	tnode(int _val): mn(_val), mx(_val), val(_val) {}
	pt pull() {
		mn = mx = val;
		for (int i = 0; i < 2; ++i) if (c[i]) {
			ckmin(mn,c[i]->mn);
			ckmax(mx,c[i]->mx);
		}
		return this;
	}
	pair<int,int> left_subtree() {
		int mn = val, mx = val;
		if (c[0]) {
			ckmin(mn,c[0]->mn);
			ckmax(mx,c[0]->mx);
		}
		return {mn,mx};
	}
	pair<int,int> right_subtree() {
		int mn = val, mx = val;
		if (c[1]) {
			ckmin(mn,c[1]->mn);
			ckmax(mx,c[1]->mx);
		}
		return {mn,mx};
	}
	void tour() {
		if (c[0]) c[0]->tour();
		cout << val << "\n";
		if (c[1]) c[1]->tour();
	}
};
 
int K;
 
pair<pt,pt> split_right(pt p, int v) {
	if (!p) return {p,p};
	pair<int,int> info = p->right_subtree();
	if (info.f >= v-K && info.s <= v+K) {
		auto [l,r] = split_right(p->c[0],v);
		p->c[0] = r;
		return {l, p->pull()};
	} else {
		auto [l,r] = split_right(p->c[1],v);
		p->c[1] = l;
		return {p->pull(),r};
	}
}
 
pair<pt,pt> split_right_2(pt p, int v) {
	if (!p) return {p,p};
	pair<int,int> info = p->left_subtree();
	if (info.s <= v) {
		auto [l,r] = split_right_2(p->c[1],v);
		p->c[1] = l;
		return {p->pull(),r};
	} else {
		auto [l,r] = split_right_2(p->c[0],v);
		p->c[0] = r;
		return {l,p->pull()};
	}
}
 
pt merge(pt l, pt r) {
	if (!l || !r) return l ?: r;
	if (l->pri > r->pri) {
		l->c[1] = merge(l->c[1],r);
		return l->pull();
	} else {
		r->c[0] = merge(l,r->c[0]);
		return r->pull();
	}
}
 
int main() {
	int N; cin >> N >> K;
	pt root = nullptr;
	while (N--) {
		int h; cin >> h;
		auto [l,r] = split_right(root,h);
		auto [r1,r2] = split_right_2(r,h);
		root = merge(l,merge(r1,merge(new tnode(h),r2)));
	}
	root->tour();
}