#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int INF = 1e9;
const int B = 100;
const int UPD = 380;
int x[MAXN], ind[MAXN];
pair<int, int> suf[MAXN];
set<pair<int, int>> s;
vector<vector<pair<int, int>>> buckets;
int n, l;
int cnt_upd = 0;
void process(int id){
auto &b = buckets[id];
if(b.empty()) return;
int sz = (int) b.size();
suf[b[sz - 1].second] = {1, l};
int r = sz - 1;
for(int i=(sz - 2); i>=0; i--){
while(b[r].first - b[i].first > l) r--;
int last = 0;
if(r < sz - 1) last = suf[b[r + 1].second].first;
int extra = (b[i].first + l) - b[sz - 1].first;
if(r < sz - 1) extra = suf[b[r + 1].second].second;
suf[b[i].second] = {last + 1, extra};
}
}
void create_buckets(){
int cnt = 0;
buckets.clear();
buckets.push_back({});
for(auto x : s){
if(cnt < B){
buckets.back().push_back(x);
cnt ++;
} else{
buckets.push_back({x});
cnt = 1;
}
ind[x.second] = (int) buckets.size() - 1;
}
for(int i=0; i<(int) buckets.size(); i++) process(i);
}
void refresh(){
cnt_upd ++;
if(cnt_upd == UPD){
create_buckets();
cnt_upd = 0;
}
}
int find_bucket(int x){
for(int i=0; i<(int) buckets.size(); i++){
if(!buckets[i].empty() && x <= buckets[i].back().first){
return i;
}
}
return (int) buckets.size() - 1;
}
void remove(int id){
int j = ind[id];
vector<pair<int, int>> cur;
for(auto x : buckets[j]){
if(x.second == id) continue;
cur.push_back(x);
}
s.erase({x[id], id});
buckets[j] = cur;
process(j);
}
void add(int id){
int j = find_bucket(x[id]);
ind[id] = j;
vector<pair<int, int>> cur;
int sz = (int) buckets[j].size();
if(sz > 0){
if(x[id] < buckets[j][0].first) cur.push_back({x[id], id});
for(int i=0; i<(sz - 1); i++){
cur.push_back(buckets[j][i]);
if(buckets[j][i].first <= x[id] && x[id] < buckets[j][i + 1].first){
cur.push_back({x[id], id});
}
}
cur.push_back(buckets[j][sz - 1]);
if(buckets[j][sz - 1].first <= x[id]) cur.push_back({x[id], id});
} else cur = {{x[id], id}};
buckets[j] = cur;
s.insert({x[id], id});
process(j);
}
int query(){
int ans = 0;
int cur = 0;
for(int i=0; i<(int) buckets.size(); i++){
if(!buckets[i].empty()){
cur = buckets[i][0].second;
break;
}
}
while(true){
ans += suf[cur].first;
int nxt = buckets[ind[cur]].back().first + suf[cur].second;
auto pos = s.upper_bound({nxt, INF});
if(pos == s.end()) break;
cur = pos->second;
}
return ans;
}
void init(int n_, int l_, int x_[]){
n = n_;
l = l_;
cnt_upd = 0;
for(int i=0; i<n; i++) x[i] = x_[i];
s.clear();
for(int i=0; i<n; i++) s.insert({x[i], i});
create_buckets();
}
int update(int id, int y){
remove(id);
x[id] = y;
add(id);
refresh();
return query();
}
