#include <bits/stdc++.h>
using namespace std;
#include "elephants.h"
const int MAX_N = 150'000, B = 400, NB = 500, INF = 2e9;
int N, L, X[MAX_N], num[MAX_N], pos[MAX_N];
vector<int> a[NB], b[NB];
void recalculate(int j) {
auto &c = a[j];
if(empty(c)) return;
int sz = size(c), pt = sz;
for(int i = sz; --i >= 0 ; ) {
while(pt && X[c[i]] + L < X[c[pt-1]]) --pt;
num[c[i]] = pt < sz ? num[c[pt]] + 1 : 1;
pos[c[i]] = pt < sz ? pos[c[pt]] : X[c[i]] + L;
}
}
void reset() {
for(int i = 0, j = 0; i < NB; i++) {
for(int &v : a[i]) pos[j++] = v;
a[i].clear();
b[i].clear();
}
for(int i = 0; i < N; i++) {
a[i/B].push_back(pos[i]);
b[i/B].push_back(X[pos[i]]);
}
for(int i = 0; i < NB; i++)
recalculate(i);
}
void init(int n, int l, int x[]) {
N = n, L = l;
for(int i = 0; i < N; i++) {
X[i] = x[i];
a[i/B].push_back(i);
}
reset();
}
int l, p, q_;
void locate(int i){
for(l=0; l < NB && size(b[l]) && b[l][0] <= X[i]; l++);
if(l) l--;
p = lower_bound(begin(b[l]), end(b[l]), X[i]) - begin(b[l]);
}
int update(int i, int y) {
locate(i);
while(a[l][p] != i) ++p;
a[l].erase(begin(a[l]) + p);
b[l].erase(begin(b[l]) + p);
recalculate(l);
X[i] = y;
locate(i);
a[l].insert(begin(a[l]) + p, i);
b[l].insert(begin(b[l]) + p, X[i]);
recalculate(l);
if(!(++q_ % B)) reset();
int res = 0, cur = -1;
for(int k = 0; k < NB; k++) {
if(empty(b[k]) || cur >= b[k].back()) continue;
int j = upper_bound(begin(b[k]), end(b[k]), cur) - begin(b[k]);
res += num[a[k][j]];
cur = pos[a[k][j]];
}
return res;
}
