#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int blsz = 300;
const int maxn = 2e5+5;
const int INF = 2e9+5;
int sp[18][maxn];
multiset<int> current;
unordered_map<int, int> vmap;
multiset<int> changed;
int A[maxn];
int dval[maxn];
int n, l;
void build_sp(){
changed = {INF};
vmap.clear();
int crr = 0;
for(auto v: current)if(!crr || dval[crr-1] != v){
vmap[v] = crr;
dval[crr++] = v;
}
for(int i = 0; i < crr-1; i++){
sp[0][i] = upper_bound(dval, dval + crr, dval[i] + l) - dval;
}
sp[0][crr-1] = crr-1;
for(int i = 1; i < 18; i++){
for(int j = 0; j < crr; j++)sp[i][j] = sp[i-1][sp[i-1][j]];
}
}
void init(int N, int L, int X[])
{
n = N;
l = L;
current.insert(INF);
for(int i = 0; i < N; i++){
A[i] = X[i];
current.insert(A[i]);
}
build_sp();
}
int update(int i, int y)
{
current.erase(current.find(A[i]));
changed.insert(A[i]);
A[i] = y;
current.insert(A[i]);
changed.insert(A[i]);
int realcnt = 0, ans = 0;
int pos = *current.begin();
while(pos != INF){
realcnt++;
if(changed.find(pos) != changed.end()){
if(current.find(pos) == current.end())pos = *current.upper_bound(pos);
else {
ans++;
pos = *current.upper_bound(pos + l);
}
}
else {
int nxt_change = *changed.upper_bound(pos);
int id = vmap[pos];
for(int i = 17; i >= 0; i--){
if(dval[sp[i][id]] < nxt_change){
id = sp[i][id];
ans += (1<<i);
}
}
pos = *current.upper_bound(dval[id] + l);
ans++;
}
}
if(realcnt >= blsz)build_sp();
return ans;
}
