#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int sqr=700,inf=2e9;
int n,l;
vector<int>x;
struct BLOCK{
vector<int>a;
vector<pair<int,int>>b;
int mx=inf;
void build(){
mx=0;
sort(begin(a),end(a));
b=vector<pair<int,int>>(a.size());
for(int i=a.size()-1,it;i>=0;--i){
it=upper_bound(begin(a),end(a),a[i]+l)-begin(a);
b[i].first=1;
b[i].second=a[i];
if(it!=a.size())b[i].first+=b[it].first,b[i].second=b[it].second;
}
}
void del(int e){
vector<int>c;
bool dl=0;
for(int i=0;i<a.size();++i){
if(a[i]!=e||dl)c.push_back(a[i]);
else dl=1;
}
assert(dl);
a=c;
build();
}
};
vector<BLOCK>B(sqr);
vector<pair<int,int>>upd;
void build(){
for(auto&i:upd)x[i.first]=i.second;
for(int i=0;i<sqr;++i)B[i].a.clear();
sort(begin(x),end(x));
for(int i=0;i<n;++i)B[i/sqr].a.push_back(x[i]);
for(int i=0;i<sqr;++i)B[i].build();
upd.clear();
}
void init(int N, int L, int X[])
{
for(int i=0;i<N;++i)x.push_back(X[i]);
n=N;
l=L;
build();
}
int find(int a){
int last=-1;
for(int i=0;i<sqr;++i){
if(!B[i].a.empty()){
last=i;
if(B[i].a.back()>=a)return i;
}
}
assert(last!=-1);
return last;
}
int update(int i, int y)
{
upd.push_back({i,y});
if(upd.size()==sqr)build();
else{
int b1=find(x[i]),b2=find(y);
B[b1/sqr].del(x[i]);
B[b2/sqr].a.push_back(y);
B[b2/sqr].build();
x[i]=y;
}
int ans=0,lf=-(2*l),it;
for(int i=0;i<sqr;++i){
if(B[i].a.empty())break;
it=upper_bound(begin(B[i].a),end(B[i].a),lf+l)-begin(B[i].a);
if(it!=B[i].a.size()){
ans+=B[i].b[it].first;
lf=B[i].b[it].second;
}
}
return ans;
}
