#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
const int MAX_N = 1000010;
#include "elephants.h"
#ifdef KEV
#include "grader.cpp"
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() {cerr << endl;}
template<class T, class ...U> void kout (T v, U ...e) { cerr << v << ' ', kout(e...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int SQ = 512, BSQ = SQ << 1;
int n, loc[MAX_N], sorted[MAX_N], Lim, blen;
struct bucket {
int xs[BSQ], need[BSQ], ed[BSQ], sz;
int minval() { return xs[0]; }
int maxval() { return xs[sz-1]; }
bool contain(int x) { return minval() <= x && x <= maxval(); }
void clear() { sz = 0; }
// they're sorted already
void init(int l, int r) {
copy(sorted + l, sorted + r, xs);
sz = r - l;
rebuild();
}
void resorted(int &pos) {
for (int i = 0;i < sz;++i)
sorted[pos++] = xs[i];
}
bool smartpb(int x) {
xs[sz++] = x;
int p = sz - 1;
while (p && xs[p] < xs[p-1])
swap(xs[p], xs[p-1]), --p;
if (sz == BSQ) return true;
rebuild();
return false;
}
// it has to exist
bool smartrm(int x) {
int p = 0;
while (xs[p] < x) ++p;
while (p + 1 < sz) xs[p] = xs[p+1], ++p;
if (--sz == 0) return true;
rebuild();
return false;
}
// when rebuild, I have xs sorted already
void rebuild() {
for (int i = sz - 1, j = sz - 1;i >= 0;--i) {
int R = xs[i] + Lim;
while (j && xs[j - 1] > R) --j;
if (R >= maxval())
need[i] = 1, ed[i] = R;
else
need[i] = 1 + need[j], ed[i] = ed[j];
}
}
void advance(int &R, int &cnt) {
int p = upper_bound(xs, xs + sz, R) - xs;
R = ed[p], cnt += need[p];
}
void out() { for (int i = 0;i < sz;++i) cerr << xs[i] << ' '; }
}buk[SQ];
void rebuildall() {
int h = 0;
for (int i = 0;i < blen;++i)
buk[i].resorted(h);
for (int id = 0;;++id) {
int L = id * SQ, R = min(h, L + SQ);
buk[id].init(L, R);
blen = id + 1;
if (R == h) break;
}
}
void remove(int x) {
for (int i = 0;i < blen;++i)
if (buk[i].contain(x)) {
if (buk[i].smartrm(x))
rebuildall();
break;
}
}
void insert(int x) {
for (int i = 0;i < blen;++i) {
if (i == blen-1 || buk[i+1].minval() > x) {
if (buk[i].smartpb(x))
rebuildall();
break;
}
}
}
int qry() {
int curR = -1, res = 0;
for (int i = 0;i < blen;++i) {
if (curR >= buk[i].maxval()) continue;
buk[i].advance(curR, res);
}
return res;
}
void init(int N, int L, int X[]) {
n = N;
Lim = L;
copy(X, X+N, loc), copy(X, X+N, sorted);
DE(N, Lim);
for (int id = 0;;++id) {
int L = id * SQ, R = min(n, L + SQ);
buk[id].init(L, R);
blen = id + 1;
if (R == n) break;
}
}
int update(int i, int y) {
if (n == 1) return 1;
remove(loc[i]);
insert(loc[i] = y);
return qry();
}
