#include <bits/stdc++.h>
#include "elephants.h"
#define all(v) begin(v), end(v)
using namespace std;
int n, l;
const int inf = 1e9 + 10;
const int maxn = 2e5 + 5;
int pos[maxn];
struct block {
int n = 0;
vector<int> x = {}, last = {}, dp = {};
block() {};
void rebuild() {
x.push_back(inf);
last.assign(n + 1, -1);
dp.assign(n + 1, 0);
int j = n;
for (int i = n - 1; i >= 0; --i) {
while (j > 0 && x[i] + l < x[j - 1]) j--;
last[i] = (j == n ? i : last[j]);
dp[i] = dp[j] + 1;
}
x.pop_back();
last.pop_back();
dp.pop_back();
}
void insert(int y) {
auto it = lower_bound(all(x), y);
x.insert(it, y);
n++;
rebuild();
}
void erase(int y) {
auto it = lower_bound(all(x), y);
x.erase(it);
n--;
rebuild();
}
};
const int B = 400;
block b[B];
void init(int N, int L, int X[]) {
n = N;
l = L;
for (int i = 0; i < n; ++i) {
pos[i] = X[i];
b[i / B].insert(pos[i]);
}
}
int it = 0;
int update(int i, int y) {
int bl = 0;
for (bl = 0; bl < B; ++bl) {
if (b[bl].x.empty() || b[bl].x.back() >= pos[i]) {
break;
}
}
b[bl].erase(pos[i]);
pos[i] = y;
for (bl = 0; bl < B; ++bl) {
if (b[bl].x.empty()) {
bl--;
break;
}
if (b[bl].x.back() >= pos[i]) {
break;
}
}
b[bl].insert(pos[i]);
int res = 0, last = -inf;
for (int bl = 0; bl < B; ++bl) {
if (b[bl].n == 0) break;
int i = upper_bound(all(b[bl].x), last + l) - b[bl].x.begin();
if (i >= b[bl].n) continue;
res += b[bl].dp[i];
last = b[bl].last[i];
}
if (it++ > B) {
for (int i = 0; i < B; ++i) {
b[i] = {};
}
for (int i = 0; i < n; ++i) {
b[i / B].insert(pos[i]);
}
}
return res;
}
