#include "elephants.h"
#include <set>
#include <algorithm>
using namespace std;
int n;
pair < int , int > all[50005];
int Next[50005];
int last[50005];
int cha[50005];
int where[50005];
int l;
void init(int N, int l, int X[])
{
int i;
n = N;
::l=l;
for(i=0;i<N;i++) all[i+1]=make_pair(X[i],i);
sort(all+1,all+N+1);
for(i=1;i<=N;i++) where[i]=all[i].first;
for(i=1;i<=N;i++) cha[all[i].second]=i;
for(i=0;i<=N;i++) Next[i]=i+1;
for(i=0;i<=N;i++) last[i]=i-1;
where[N+1]=2e9;
}
int update(int i, int y)
{
int now=0,a,b,here,ll;
i=cha[i];
//printf("%d %d\n",i,y);
a=last[i];
b=Next[i];
Next[a]=b;
last[b]=a;
here=0;
while(1)
{
if(where[Next[here]]>y)
{
a=here;
b=Next[here];
Next[a]=i;
Next[i]=b;
last[b]=i;
last[i]=a;
break;
}
here=Next[here];
}
where[i]=y;
here=Next[0];
ll=where[here];
now=1;
while(here!=n+1)
{
//printf("%d\n",where[here]);
if(where[here]-ll>l)
{
now++;
ll=where[here];
}
here=Next[here];
}
return now;
}
