#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define sz(x) ((int) (x).size())
#define all(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
template <class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) return x = y, true;
else return false;
}
int n, d;
const int maxn = (int) 100 + 2;
const int LOG = 18;
int a[maxn + 2], dp[maxn + 2];
int st[maxn + 2][LOG + 1];
int f[maxn + 2][LOG + 1];
int minPos[maxn + 2];
vector <int> tree[4 * maxn + 7];
int seg[4 * maxn + 7];
// ----------- SEGMENT TREE ---------------------- //
void update(int pos, int v) {
int id = 1, l = 1, r = n;
while (l < r) {
int g = (l + r) >> 1;
if (g >= pos) {
id = 2 * id;
r = g;
} else {
id = 2 * id + 1;
l = g + 1;
}
}
maximize(seg[id], v);
while (id > 1) {
id >>= 1;
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
}
int get(int id, int l, int r, int u, int v) {
if (l > v || u > r) return 0;
if (u <= l && r <= v) return seg[id];
int g = (l + r) >> 1;
return max(get(id << 1, l, g, u, v), get(id << 1 | 1, g + 1, r, u, v));
}
// ----------- SEGMENT TREE ---------------------- //
namespace subtask6 {
void prepare() {
FOR(i, 1, n) st[i][0] = a[i];
FOR(j, 1, LOG)
FOR(i, 1, n - MASK(j) + 1)
st[i][j] = min(st[i][j - 1], st[i + MASK(j - 1)][j - 1]);
}
int getmin(int l, int r) {
int k = __lg(r - l + 1);
return min(st[l][k], st[r - MASK(k) + 1][k]);
}
void process() {
FOR(j, 1, LOG)
for (int i = 1; i <= n; ++i) {
st[i][j] = st[st[i][j - 1]][j - 1];
f[i][j] = max(f[i][j - 1], f[st[i][j - 1]][j - 1]);
}
}
int findPos(int i) {
int val = a[i];
for (int j = LOG; j >= 0; --j) {
if (f[i][j] < val && f[i][j] > 0) {
i = st[i][j];
}
}
return i;
}
#define vi vector <int>
vi mer(vi &x, vi &y) {
vi res;
int i = 0, j = 0;
while (i < sz(x) && j < sz(y)) {
if (x[i] <= y[j]) res.push_back(x[i++]);
else res.push_back(y[j++]);
}
while (i < sz(x)) res.push_back(x[i++]);
while (j < sz(y)) res.push_back(y[j++]);
return res;
}
void updateINC(int pos, int val) {
int id = 1, l = 1, r = n;
while (l < r) {
int g = (l + r) >> 1;
if (g >= pos) {
id = 2 * id;
r = g;
} else {
id = 2 * id + 1;
l = g + 1;
}
}
tree[id].push_back(val);
while (id > 1) {
id >>= 1;
tree[id] = mer(tree[id << 1], tree[id << 1 | 1]);
}
}
int GET(int id, int l, int r, int u, int v, int x) {
if (l > v || u > r) return 0;
if (u <= l && r <= v) {
int lo = 0, hi = sz(tree[id]) - 1, m, vt = -1;
while (lo <= hi) {
m = (lo + hi) >> 1;
if (tree[id][m] < x) vt = m, lo = m + 1;
else hi = m - 1;
}
return (~vt ? tree[id][vt] : 0);
}
int g = (l + r) >> 1;
return max(GET(id << 1, l, g, u, v, x), GET(id << 1 | 1, g + 1, r, u, v, x));
}
void solve() {
prepare();
FOR(i, 2, n) {
int l = max(1, i - d), r = i - 1, g, vt = -1;
int x = getmin(l, r);
while (l <= r) {
g = (l + r) >> 1;
if (getmin(g, i - 1) > x) r = g - 1;
else vt = g, l = g + 1;
}
minPos[i] = vt;
}
minPos[1] = 1;
FOR(i, 1, n) st[i][0] = minPos[i], f[i][0] = a[minPos[i]];
process();
FOR(i, 1, n) minPos[i] = findPos(i);
prepare();
FOR(i, 1, n) {
dp[i] = 1;
int j = minPos[i];
if (j != i) {
int x = GET(1, 1, n, j, i - 1, a[i]);
int y = getmin(j, i - 1);
dp[i] = get(1, 1, n, y, x) + 1;
}
update(a[i], dp[i]);
updateINC(i, a[i]);
}
// cout << *max_element(dp + 1, dp + 1 + n);
FOR(i, 1, n) cout << a[i] << " " << dp[i] << "\n";
}
};
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> d;
vector <int> v;
FOR(i, 1, n) cin >> a[i], v.push_back(a[i]);
sort(all(v));
v.erase(unique(all(v)), v.end());
FOR(i, 1, n) a[i] = lower_bound(all(v), a[i]) - v.begin() + 1;
subtask6 :: solve();
return 0;
}
