#include "elephants.h"
#include <math.h>
const int N_ = 150050;
const int SN = 400;
int bk_sz, counter, L, N;
int D[N_], tmp[N_];
struct Group{
Group(){
for(int i=0;i<SN*2;i++)w[i]=c[i]=en[i]=0;
sz=0;
}
int w[SN*2], en[SN*2], c[SN*2];
int sz;
void fix(){
int s;
for(s=sz-1;s!=-1 && w[sz-1] - w[s] <= L;s--)c[s] = 1, en[s] = w[s] + L;
for(int e = sz-1;s!=-1;s--){
while(w[e] - w[s] > L)e--;
c[s] = c[e+1] + 1;
en[s] = en[e+1];
}
}
void update(int v){
int i, ins;
for(ins=0;w[ins]<=v && ins!=sz;ins++);
sz++;
for(i=sz-1;i>ins;i--)w[i] = w[i-1];
w[ins] = v;
fix();
}
void del(int v){
int i, d=0;
while(w[d] != v)d++;
sz--;
for(i=d;i<sz;i++)w[i] = w[i+1];
w[sz] = 0;
fix();
}
};
struct elephants{
elephants(){
for(int i=0;i<SN;i++)gr[i] = Group();
sz=0;
}
Group gr[SN+10];
int sz;
void init(){
int i,now=0,cnt=0;
for(i=0;i<N;i++){
if(cnt == bk_sz)gr[now].sz = cnt, gr[now++].fix(), cnt = 0;
gr[now].w[cnt++] = D[i];
}
gr[now].sz = cnt, gr[now].fix(), sz = now + 1;
}
void fix(){
int len = 0;
for(int i=0;i<sz;i++)for(int j=0;j<gr[i].sz;j++)tmp[len++] = gr[i].w[j];
int now=0,cnt=0;
for(int i=0;i<N;i++){
if(cnt == bk_sz)gr[now].sz = cnt, gr[now++].fix(), cnt = 0;
gr[now].w[cnt++] = tmp[i];
}
gr[now].sz = cnt, gr[now].fix(), sz = now + 1;
}
void update(int v){
int ins=1;
for(;ins<sz && gr[ins].w[0] <= v;ins++);
gr[ins-1].update(v);
}
void del(int v){
int d = 0;
for(;gr[d].sz && gr[d].w[0] <= v;d++);
gr[d-1].del(v);
}
int get_ans(){
int i, ret = 0, now, en = -1;
for(i=0;i<sz;i++){
int s=0, e=gr[i].sz-1;
if(gr[i].w[e] <= en)continue;
while(s<=e){
int m=(s+e)>>1;
if(gr[i].w[m] > en)now=m, e=m-1;
else s=m+1;
}
ret += gr[i].c[now];
en = gr[i].en[now];
}
return ret;
}
};
elephants Ep;
void init(int N, int L, int X[])
{
::N = N, ::L = L;
bk_sz = sqrt(N);
for(int i=0;i<N;i++)D[i] = X[i];
Ep.init();
}
int update(int i, int y)
{
Ep.update(y);
Ep.del(D[i]);
D[i] = y;
if(++counter == bk_sz)Ep.fix(), counter = 0;
return Ep.get_ans();
}
