#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
int k = 400;
int n, l, t;
set<pair<int,int>> e;
vector<int> pos, eb;
struct bucket {
set<pair<int,int>> es;
unordered_map<int,pair<int,int>> res;
bucket(){};
};
vector<bucket*> buckets;
void calc(bucket* 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);
for (int i=0; i<=n/k; i++) buckets.push_back(new bucket());
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();
}
