#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN = 150000;
int N, L;
v<int> E;
void init(int n, int l, int X[])
{
N = n;
L = l;
for(int i=0; i<N; i++) E.push_back(X[i]);
}
const int BUCK = 400;
int qNum = 0;
v<int> buckInd(MAXN);
v<v<ii>> bucks(MAXN/BUCK + 1);
v<v<ii>> bucksAns(MAXN/BUCK+1);
void rebuildBuck(int b){
bucksAns[b].resize(bucks[b].size(), {0,0});
for(int i=bucks[b].size()-1; i>=0; i--){
auto it = lower_bound(bucks[b].begin()+i+1, bucks[b].end(), make_pair(bucks[b][i].fi+L+1, -1));
if(it==bucks[b].end()) bucksAns[b][i] = {1, bucks[b][i].fi+L+1};
else{
ii tmp = bucksAns[b][distance(bucks[b].begin(), it)];
bucksAns[b][i] = {1 + tmp.fi, tmp.se};
}
}
}
void rebuild(){
v<ii> e;
for(int i=0; i<N; i++) e.push_back({E[i], i});
sort(e.begin(), e.end());
for(int i=0; i<bucks.size(); i++) bucks[i].clear();
int b=0;
for(auto it:e){
if(bucks[b].size()==BUCK) b++;
bucks[b].push_back(it);
buckInd[it.se] = b;
}
for(int i=0; i<bucks.size(); i++) rebuildBuck(i);
}
void move(int e, int x){
int b = buckInd[e];
bucks[b].erase(find(bucks[b].begin(), bucks[b].end(), make_pair(E[e], e)));
rebuildBuck(b);
E[e] = x;
int l=0, r=bucks.size()-1;
while(l<r){
int m=(l+r+1)/2;
if(bucks[m].size()>0 && bucks[m][0].fi<=x) l=m;
else r=m-1;
}
auto it = upper_bound(bucks[l].begin(), bucks[l].end(), make_pair(x, e));
bucks[l].insert(it, {x, e});
buckInd[e] = l;
rebuildBuck(l);
}
int ans(){
int cur = 0;
int ret = 0;
for(int b=0; b<bucks.size(); b++){
auto it = lower_bound(bucks[b].begin(), bucks[b].end(), make_pair(cur, -1));
if(it!=bucks[b].end()){
int i = distance(bucks[b].begin(), it);
ret += bucksAns[b][i].fi;
cur = bucksAns[b][i].se;
}
}
return ret;
}
void debug(int b){
for(int i=0; i<bucks[b].size(); i++) cout<<bucks[b][i].fi<<" "<<bucks[b][i].se<<" "<<bucksAns[b][i].fi<<" "<<bucksAns[b][i].se<<endl;
cout<<endl;
}
int update(int i, int y){
if((qNum++)%BUCK==0) rebuild();
move(i, y);
return ans();
}
