#include"elephants.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int BUCKET_SIZE=256;
ll n,l;
ll pos[150000];
struct Bucket{
vector<ll>arr;
vector<ll>num;
vector<ll>pos;
void regen(){
num.resize(arr.size());
pos.resize(arr.size());
for(int i=(int)arr.size()-1;i>=0;i--){
num[i]=1;
ll p=arr[i]+l;
if(p>=arr.back()){
pos[i]=p;
continue;
}
int l=i-1,r=(int)arr.size()-1;
while(l<r-1){
int m=(l+r)/2;
if(arr[m]<=p)
l=m;
else
r=m;
}
num[i]=num[r]+1;
pos[i]=pos[r];
}
}
void erase(int el){
auto it=lower_bound(arr.begin(),arr.end(),el);
arr.erase(it);
regen();
}
void add(int el){
auto it=upper_bound(arr.begin(),arr.end(),el);
arr.insert(it,el);
regen();
}
pair<ll,ll>get(ll p){
if(arr.empty()||p>=arr.back())
return{0,p};
int l=-1,r=(int)arr.size()-1;
while(l<r-1){
int m=(l+r)/2;
if(arr[m]<=p)
l=m;
else
r=m;
}
return{num[r],pos[r]};
}
};
vector<Bucket*>buckets;
void init(int N,int L,int X[]){
n=N;
l=L;
vector<int>vec;
for(int i=0;i<n;i++){
pos[i]=X[i];
vec.push_back(X[i]);
}
sort(vec.begin(),vec.end());
buckets.push_back(new Bucket);
for(int i:vec){
buckets.back()->arr.push_back(i);
if((int)buckets.back()->arr.size()>=BUCKET_SIZE){
buckets.push_back(new Bucket);
}
}
for(auto i:buckets)
i->regen();
}
int update(int i,int y){
// balance buckets
for(int i=0;i<(int)buckets.size();i++){
if(buckets[i]->arr.size()>=2*BUCKET_SIZE){
buckets.insert(buckets.begin()+i+1,new Bucket);
buckets[i+1]->arr={buckets[i]->arr.begin()+buckets[i]->arr.size()/2,buckets[i]->arr.end()};
buckets[i]->arr.erase(buckets[i]->arr.begin()+buckets[i]->arr.size()/2,buckets[i]->arr.end());
buckets[i]->regen();
buckets[i+1]->regen();
}
}
for(auto b:buckets){
if(b->arr.size()&&b->arr[0]<=pos[i]&&pos[i]<=b->arr.back()){
b->erase(pos[i]);
break;
}
}
pos[i]=y;
int cb=0;
while(cb<(int)buckets.size()){
if(!buckets[cb]->arr.empty()&&buckets[cb]->arr[0]>=y)
break;
cb++;
}
if(cb)
cb--;
buckets[cb]->add(y);
ll pos=-1,res=0;
for(auto b:buckets){
auto r=b->get(pos);
res+=r.first;
pos=r.second;
}
return res;
}
