#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define es first
#define res second
int k = 400;
int n, l, t;
set<pair<int,int>> e;
vector<int> pos, eb;
vector<pair<set<pair<int,int>>, unordered_map<int,pair<int,int>>>> buckets;
void calc(pair<set<pair<int,int>>, unordered_map<int,pair<int,int>>>& b){
auto it = b.es.end();
while (it != b.es.begin()){
it--;
auto next = b.es.upper_bound({it->first+l, 1000000});
if (next == b.es.end()) b.res[it->second] = {1, it->first+l};
else b.res[it->second] = {1+b.res[next->second].first, b.res[next->second].second};
}
}
void build(){
int ct = 0, cb = 0;
auto it = e.begin();
buckets[0].es.clear();
buckets[0].res.clear();
while (it != e.end()){
buckets[cb].es.insert(*it);
eb[it->second] = cb;
it++;
ct++;
if (ct == k){
ct = 0;
cb++;
buckets[cb].es.clear();
buckets[cb].res.clear();
}
}
for (auto b : buckets) calc(b);
}
int solve(){
int ans = 0;
auto cur = e.begin();
while (cur != e.end()){
pair<int,int> jump = buckets[eb[cur->second]].res[cur->second];
ans += jump.first;
cur = e.upper_bound({jump.second, 1000000});
}
return ans;
}
void init(int N, int L, int X[]){
n = N;
l = L;
pos.resize(n);
for (int i=0; i<N; i++){
pos[i] = X[i];
e.insert({X[i], i});
}
eb.resize(n);
set<pair<int,int>> emptyset;
unordered_map<int,pair<int,int>> emptymap;
for (int i=0; i<=n/k; i++) buckets.push_back({emptyset, emptymap});
build();
t = 0;
}
int update(int i, int y){
t++;
if (t == 4*k){
e.erase({pos[i], i});
pos[i] = y;
e.insert({pos[i], i});
t = 0;
build();
return solve();
}
buckets[eb[i]].es.erase({pos[i], i});
calc(buckets[eb[i]]);
e.erase({pos[i], i});
pos[i] = y;
e.insert({pos[i], i});
int nb = 0;
for (int pb = 1; pb < buckets.size(); pb++){
if (!buckets[pb].es.empty()){
if (buckets[pb].es.begin()->first <= pos[i]) nb = pb;
else break;
}
}
buckets[nb].es.insert({pos[i], i});
eb[i] = nb;
calc(buckets[nb]);
return solve();
}
