#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, sq, l, rea[150010], eleph[150010], basnum, updatenum;
struct data
{
int el[1600], siz;
int next[1600], cost[1600];
void in_init(int p)
{
el[++siz]=p;
}
void get_arr()
{
for(int here=siz; here>=1; here--){
int ne=el[here]+l+1;
if(ne>el[siz]){
cost[here]=1;
next[here]=ne;
}
else{
int dow=lower_bound(el, el+siz+1, ne)-el;
cost[here]=cost[dow]+1;
next[here]=next[dow];
}
}
}
void in(int p)
{
int here;
if(!siz)here=1;
else here=lower_bound(el, el+siz+1, p)-el;
here=max(here, 1);
for(int i=siz; i>=here; i--)el[i+1]=el[i], next[i+1]=next[i], cost[i+1]=cost[i];
el[here]=p;
siz++;
get_arr();
}
void out(int p)
{
int here=lower_bound(el, el+siz+1, p)-el;
for(int i=here+1; i<=siz; i++){
el[i-1]=el[i];
next[i-1]=next[i];
cost[i-1]=cost[i];
}
siz--;
get_arr();
}
int find_pl(int p){
return lower_bound(el+1, el+siz+1, p)-el;
}
}bas[1000];
void in_basket()
{
basnum=1;
for(int i=1; i<=n; i++){
bas[basnum].in_init(rea[i]);
if(i%sq==0&&i!=n)basnum++;
}
for(int i=1; i<=basnum; i++)
bas[i].get_arr();
}
void init(int N, int L, int X[])
{
n=N;
l=L;
sq=600;
for(int i=0; i<n; i++)rea[i+1]=eleph[i]=X[i];
sort(rea+1, rea+n+1);
in_basket();
//puts("");
}
int find_basket(int st, int fin, int num)
{
if(st==fin)return st;
int mid=(st+fin)/2+1;
if(bas[mid].el[1]>num)return find_basket(st, mid-1, num);
return find_basket(mid, fin, num);
}
int f(int basketnum, int pl)
{
if(basketnum>basnum)return 0;
if(bas[basketnum].el[bas[basketnum].siz]<pl||bas[basketnum].siz==0)return f(basketnum+1, pl);
int p=bas[basketnum].find_pl(pl);
//if(updatenum==41)printf("%d, %d\n", bas[basketnum].el[p], bas[basketnum].cost[p]);
return bas[basketnum].cost[p]+f(basketnum+1, bas[basketnum].next[p]);
}
int update(int i, int y)
{
updatenum++;
if(updatenum%sq){
int wbas, to;
if(bas[basnum].siz){
wbas=find_basket(1, basnum, eleph[i]);
to=find_basket(1, basnum, y);
}
else{
wbas=find_basket(1, basnum-1, eleph[i]);
to=find_basket(1, basnum-1, y);
}
bas[wbas].out(eleph[i]);
bas[to].in(y);
eleph[i]=y;
}
else{
eleph[i]=y;
for(int i=0; i<n; i++)rea[i+1]=eleph[i];
sort(rea+1, rea+n+1);
for(int i=1; i<=basnum; i++)bas[i].siz=0;
in_basket();
}
return f(1, bas[1].el[1]);
}
