#include "elephants.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=15e4;
//const int S=400; // how many in one block
const int S=2;
int l;
struct Block
{
int d;
int t[2*S+10];
pair<int,int> dp[2*S+10];
Block()
{
d=0;
}
void clear()
{
d=0;
return;
}
void recount()
{
dp[d]={0,0};
for(int i=d-1,j=d;i>=0;i--)
{
while(t[i]+l<t[j-1])
j--;
dp[i].fi=dp[j].fi+1;
if(j==d)
dp[i].se=t[i]+l;
else
dp[i].se=dp[j].se;
}
return;
}
void add(int x)
{
int p;
for(p=0;p<d && t[p]<x;p++);
for(int i=d-1;i>=p;i--)
t[i+1]=t[i];
t[p]=x;
d++;
recount();
return;
}
void remove(int x)
{
int p;
for(p=0;p<d && t[p]<x;p++);
for(int i=p;i<d-1;i++)
t[i]=t[i+1];
d--;
recount();
return;
}
pair<int,int> ans_pos(int x)
{
if(d==0)
return {0,x};
int bg=0,en=d-1;
while(bg<en)
{
int mid=(bg+en)/2;
if(t[mid]>x)
en=mid;
else
bg=mid+1;
}
if(t[bg]<=x)
return {0,x};
return dp[bg];
}
};
int n,qq=0;
Block b[NN/S+10];
int curr_pos[NN+10];
void recount_all()
{
for(int i=0;i<=n/S;i++)
b[i].clear();
vector<int> tmp(n);
for(int i=0;i<n;i++)
tmp[i]=curr_pos[i];
sort(tmp.begin(),tmp.end());
for(int i=0;i<n;i++)
{
b[i/S].t[i%S]=tmp[i];
b[i/S].d++;
}
for(int i=0;i<=n/S;i++)
b[i].recount();
return;
}
Block& find_block(int x)
{
int i;
for(i=0;b[i].d>0 && b[i].t[0]<x;i++);
if(i==0)
return b[0];
return b[i-1];
}
int get_ans()
{
int ans=0,x=-1;
for(int i=0;i<=n/S;i++)
{
auto tmp=b[i].ans_pos(x);
ans+=tmp.fi;
x=tmp.se;
//cerr<<"xd "<<i<<" "<<ans<<" "<<x<<"\n";
//for(int j=0;j<b[i].d;j++)
// cerr<<b[i].t[j]<<" ";
//cerr<<"\n";
}
return ans;
}
void init(int N,int L,int X[])
{
n=N;
l=L;
for(int i=0;i<n;i++)
curr_pos[i]=X[i];
recount_all();
return;
}
int update(int i,int y)
{
if(qq>=S-10)
{
recount_all();
qq=0;
}
qq++;
find_block(curr_pos[i]).remove(curr_pos[i]);
find_block(y).add(y);
curr_pos[i]=y;
return get_ans();
}
