#include "elephants.h"
#include <iostream>
const int nmax=150005;
const int buck=800;
const int B=3200;
using namespace std;
pair<int,int> dp[B][B],b[B][B];
pair<int,int> unde[nmax],v[nmax];
int lg[nmax];
int sz[B];
int n,m,i,j,L,bucks,actbucks;
void baga(int wh,int x,int poz)
{
sz[wh]++;
for(int p=sz[wh];p>=1;p--)
{
if(b[wh][p-1].first<=x)
{
b[wh][p]={x,poz};
unde[poz]={wh,p};
return;
}
b[wh][p]=b[wh][p-1];
unde[b[wh][p].second]={wh,p};
}
}
int cb(int wh,int val)
{
//resturneaza pozitia primului element mai mare ca val din bucketul wh
int ret=0;
for(int p=lg[sz[wh]];p>=0;p--)
if(ret+(1<<p)<=sz[wh]&&b[wh][ret+(1<<p)].first<=val)
ret+=(1<<p);
ret++;
return ret;
}
void recalc(int wh)
{
int poz=0;
b[wh][sz[wh]+1].first=2*1000*1000*1000+5;poz=sz[wh]+1;
for(int i=sz[wh];i>=1;i--)
{
while(b[wh][poz].first>b[wh][i].first+L)
poz--;
if(b[wh][i].first+L>=b[wh][poz].first)
poz++;
if(poz<=sz[wh])
{
dp[wh][i]=dp[wh][poz];
dp[wh][i].first++;
}
else
{
dp[wh][i]={1,b[wh][i].first+L};
}
}
}
void sterge(int wh,int pp)
{
for(int p=pp;p<sz[wh];p++)
{
unde[b[wh][p+1].second]={wh,p};
b[wh][p]=b[wh][p+1];
}
sz[wh]--;
recalc(wh);
return;
}
void ins(int poz,int x)
{
int wh=0;
for(int i=1;i<=actbucks&&wh==0;i++)
{
if(b[i][sz[i]].first>=x)
{
baga(i,x,poz);
wh=i;
}
}
if(wh==0)
{
actbucks++;
wh=actbucks;
baga(wh,x,poz);
}
recalc(wh);
}
int rec_all()
{
int ret=0,act=0,poz;
for(int i=1;i<=bucks;i++)
if(sz[i])
{
if(ret==0)
{
act=dp[i][1].second;
ret=dp[i][1].first;
}
else
{
poz=cb(i,act);
if(poz<=sz[i])
{
ret+=dp[i][poz].first;
act=dp[i][poz].second;
}
}
}
return ret;
}
void rebucket()
{
bucks=(n/buck+1)+buck;int nr=1;
actbucks=0;
for(int i=1;i<=bucks;i++)
{
sz[i]=0;
for(j=nr;j<=min(nr+buck-1,n);j++)
{
baga(i,v[j].first,v[j].second);
}
if(nr<=n) actbucks++;
nr+=buck;
recalc(i);
}
rec_all();
}
void init(int N, int Lo, int X[])
{
n = N;L=Lo;
for(i=2;i<=n;i++)
lg[i]=lg[i/2]+1;
for(i=1;i<=n;i++)
v[i].first=X[i-1],v[i].second=i;
rebucket();
}
int cate=0;
int update(int i, int y)
{
cate++;i++;
if(cate%buck==0)
{
int nr=0;
for(int ii=1;ii<=actbucks;ii++)
for(int jj=1;jj<=sz[ii];jj++)
v[++nr]=b[ii][jj];
rebucket();
}
sterge(unde[i].first,unde[i].second);
ins(i,y);
return rec_all();
}
