#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int sq = 400;
int X[150015], L;
struct group {
int x[808], p[808], r[808], sz;
void update() {
for(int i=sz-1, j=sz;i>=0;i--) {
while(j > i && x[j-1]-x[i] > L) j--;
if(j == sz) r[i] = x[i], p[i] = 1;
else r[i] = r[j], p[i] = p[j]+1;
}
}
void add(int u) {
x[sz++] = u;
for(int i=sz-1;i>0;i--) if(x[i] < x[i-1]) swap(x[i], x[i-1]);
update();
}
void erase(int u) {
int k = 0;
while(x[k] != u) k++;
for(int i=k+1;i<sz;i++) swap(x[i-1], x[i]);
sz--;
update();
}
} g[404];
int N, cnt, P[150015];
void rebuild() {
int c = 0;
for(int i=0;i<sq;i++) for(int j=0;j<g[i].sz;j++) P[c++] = g[i].x[j];
for(int i=0;i<=(N-1)/sq;i++) g[i].sz = 0;
for(int i=0;i<N;i++) g[i/sq].x[g[i/sq].sz++] = P[i];
for(int i=0;i<=(N-1)/sq;i++) g[i].update();
}
void init(int N, int L, int X[]) {
::L = L, ::N = N;
memcpy(::X, X, sizeof(int)*N), memcpy(P, X, sizeof(int)*N);
rebuild();
}
int get_group(int x) {
int re = sq-1;
while(re && (!g[re].sz || x < g[re].x[0])) re--;
return re;
}
int update(int i, int y) {
g[get_group(X[i])].erase(X[i]);
X[i] = y, g[get_group(y)].add(y);
if(++cnt == sq) rebuild(), cnt = 0;
int ans = 0, R = -1;
for(int i=0;i<sq;i++) if(g[i].sz && R < g[i].x[g[i].sz-1]) {
int s = 0, e = g[i].sz-1;
while(s <= e) {
int mid = (s+e) >> 1;
if(g[i].x[mid] <= R) s = mid+1;
else e = mid-1;
}
ans += g[i].p[s], R = g[i].r[s]+L;
}
return ans;
}
