#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int blockSize = 500, resetCycle = 200, mn = 150'005;
int n, L, queryCount, save[mn];
struct block {
vector<int> x, jumpTo, step;
void refine() {
int iter = x.size();
for (int i = (int)x.size() - 1; i >= 0; i--) {
while (iter - 1 >= 0 && x[iter - 1] - x[i] > L) iter--;
if (iter == x.size()) jumpTo[i] = x[i] + L, step[i] = 1;
else jumpTo[i] = jumpTo[iter], step[i] = step[iter] + 1;
}
}
block (vector<int> x) : x(x), jumpTo(x.size()), step(x.size()) { refine(); }
void insert (int xP) {
x.insert(upper_bound(all(x), xP), xP);
jumpTo.push_back(0), step.push_back(0);
refine();
}
void remove (int xP) {
x.erase(lower_bound(all(x), xP));
jumpTo.pop_back(), step.pop_back();
refine();
}
pii batchJump (int start) {
int pos = upper_bound(all(x), start) - x.begin();
if (pos == x.size()) return {start, 0};
return {jumpTo[pos], step[pos]};
}
int last() { return x.back(); }
};
vector<block> blocks;
void build (const vector<int> &x) {
for (int i = 0; i < x.size(); i += blockSize) {
vector<int> cur(x.begin() + i, x.begin() + min((int)x.size(), i + blockSize));
blocks.emplace_back(cur);
}
}
void reBuild() {
vector<int> x;
for (block &cur : blocks)
for (int u : cur.x) x.push_back(u);
blocks.clear(), build(x);
}
void insert (int xP) {
for (block &cur : blocks)
if (cur.last() >= xP) return cur.insert(xP), void();
blocks[(int)blocks.size() - 1].insert(xP);
}
void remove (int xP) {
for (block &cur : blocks)
if (cur.last() >= xP) return cur.remove(xP), void();
}
int query() {
int curPos = -1, ans = 0;
for (block &cur : blocks) {
int newPos, step; tie(newPos, step) = cur.batchJump(curPos);
curPos = newPos, ans += step;
}
return ans;
}
void init (int _n, int _L, int X[]) {
n = _n, L = _L;
vector<int> vec(n);
for (int i = 0; i < n; i++) vec[i] = save[i] = X[i];
build(vec);
}
int update (int i, int y) {
if (queryCount && queryCount % resetCycle == 0) reBuild();
queryCount++, remove(save[i]), insert(y), save[i] = y;
return query();
}
