#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 150005
#define B 1600
int n,k,bs[MAX_N/B+1],p[MAX_N],pl[MAX_N],l,cnt,ds[MAX_N/B+1][B*2+1],sz[MAX_N/B+1][B*2+1],el[MAX_N/B+1][B*2+1];
void Bini(int x,int *xel,int xbs,int *xds,int *xsz){
sort(xel,xel+xbs);
int r=xbs;
for(int i=xbs-1;i>=0;i--){
while(r-1>=0&&xel[i]+l<xel[r-1])r--;
if(r==xbs){
xds[i]=xel[i]+l;
xsz[i]=1;
}else{
xds[i]=xds[r];
xsz[i]=xsz[r]+1;
}
}
}
void ALLini(void){
for(int i=0;i<n;i++)pl[i]=p[i];
sort(pl,pl+n);
bs[0]=0;
k=0;
for(int i=0;i<n;i++){
if(bs[k]>=B){
k++;
bs[k]=0;
}
el[k][bs[k]]=pl[i];
bs[k]++;
}
for(int i=0;i<=k;i++)Bini(i,el[i],bs[i],ds[i],sz[i]);
}
void init(int N, int L, int X[]){
n=N,l=L;
for(int i=0;i<n;i++)p[i]=X[i];
ALLini();
}
int update(int t, int y){
int a=-1,b=p[t];
while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=b))a++;
if(a==-1)a=0;
for(int i=0;i<bs[a]-1;i++){
if(el[a][i]==b){
el[a][i]=el[a][bs[a]-1];
break;
}
}
bs[a]--;
Bini(a,el[a],bs[a],ds[a],sz[a]);
p[t]=y;
a=-1;
while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0]<=y))a++;
if(a==-1)a=0;
el[a][bs[a]]=y;
bs[a]++;
Bini(a,el[a],bs[a],ds[a],sz[a]);
int ans=0;
a=0,b=-1;
for(;a<=k;a++){
if(bs[a]==0)continue;
int c=upper_bound(el[a],el[a]+bs[a],b)-el[a];
if(c==bs[a])continue;
ans+=sz[a][c];
b=ds[a][c];
}
cnt++;
if(cnt>=B/2){
cnt=0;
ALLini();
}
return ans;
}
