#include <bits/stdc++.h>
#include "elephants.h"
#define all(a) (a).begin(), (a).end()
using namespace std;
const int N = 15e4;
const int SZ = 200;
vector <int> pos[3 * N / SZ];
vector <pair <int, int>> dp[3 * N / SZ];
int x[N];
int length, nb_blocks;
void compute(int id) {
int sz = (int)size(pos[id]);
dp[id].resize(sz);
for (int nxt = sz, i = sz - 1; ~i; i --) {
while (pos[id][nxt - 1] > pos[id][i] + length)
nxt --;
dp[id][i] = (nxt == sz) ? make_pair(1, pos[id][i] + length) : make_pair(1 + dp[id][nxt].first, dp[id][nxt].second);
}
return;
}
void upd(int v, bool add) {
int id = 0;
while (id < nb_blocks - 1 && pos[id].back() < v)
id ++;
if (add)
pos[id].insert(lower_bound(all(pos[id]), v), v);
else
pos[id].erase(lower_bound(all(pos[id]), v));
if (pos[id].size() == 2 * SZ) {
for (int i = nb_blocks ++; i > id + 1; i --) {
swap(pos[i], pos[i - 1]);
swap(dp[i], dp[i - 1]);
}
pos[id + 1].insert(pos[id + 1].begin(), pos[id].begin() + SZ, pos[id].end());
pos[id].erase(pos[id].begin() + SZ, pos[id].end());
compute(id + 1);
}
if (pos[id].empty()) {
-- nb_blocks;
for (int i = id; i < nb_blocks; i ++) {
swap(pos[i], pos[i + 1]);
swap(dp[i], dp[i + 1]);
}
}
else
compute(id);
/*for (int i = 0; i < nb_blocks - 1; i ++) {
if ((int)size(pos[i]) + (int)size(pos[i + 1]) <= SZ) {
pos[i].insert(pos[i].end(), all(pos[i + 1]));
pos[i + 1].clear();
dp[i + 1].clear();
-- nb_blocks;
for (int j = i + 1; j < nb_blocks; j ++) {
swap(pos[j], pos[j + 1]);
swap(dp[j], dp[j + 1]);
}
compute(i);
}
}*/
return;
}
int answer() {
int ans = dp[0][0].first, cur = dp[0][0].second;
for (int id = 1; id < nb_blocks; id ++) {
if (pos[id].back() <= cur)
continue;
int i = upper_bound(all(pos[id]), cur) - pos[id].begin();
ans += dp[id][i].first;
cur = dp[id][i].second;
}
return ans;
}
void init(int N, int L, int X[]) {
length = L;
nb_blocks = (SZ - 1 + N) / SZ;
for (int i = 0; i < N; i ++)
pos[i / SZ].push_back(x[i] = X[i]);
for (int i = 0; i < nb_blocks; i ++)
compute(i);
return;
}
int update(int id, int nv) {
upd(x[id], 0);
upd(x[id] = nv, 1);
return answer();
}
