#include "elephants.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,l,arr[MAXN],asked=1,cur;
int sz[MAXN],where[MAXN];
PII tmp[MAXN];
const int BLOK=500;
vector<PII>dp[MAXN/BLOK+3],s[MAXN/BLOK+3];
void build(int block){
sort(all(s[block]));
dp[block].resize(sz[block]);
int p=sz[block]-1;
for(int i=0;i<sz[block];i++)
dp[block][i]=mp(0,i);
for(int i=sz[block]-1;i>=0;i--){
while(s[block][i].ff+l<s[block][p].ff)p--;
if(p+1<sz[block])dp[block][i]=mp(dp[block][p+1].ff+1,dp[block][p+1].ss);
}
}
int query(){
int last=-1,ans=0;
for(int i=0;i<cur;i++)
if(sz[i]){
int pos=upper_bound(all(s[i]),mp(last,INF))-s[i].begin();
if(pos<sz[i]){
if(dp[i][pos].ff)
ans+=dp[i][pos].ff,pos=dp[i][pos].ss;
last=s[i][pos].ff+l;ans++;
}
}
return ans;
}
void init(int N, int L, int X[]){
for(int i=0;i<cur;i++)
s[i].clear(),sz[i]=0;
n = N; l = L; cur=0;
for(int i=0;i<n;i++){
arr[i]=X[i];
tmp[i]=mp(X[i],i);
}
sort(tmp,tmp+N);
for(int i=0;i<n;i++){
where[tmp[i].ss]=cur;
s[cur].pb(tmp[i]);
sz[cur]++;
if((i+1)%BLOK==0)
cur++;
}if(n%BLOK!=0)cur++;
for(int i=0;i<cur;i++)
build(i);
}
void poz(int block,PII val){
for(int i=0;i<int(s[block].size());i++)
if(s[block][i]==val){
s[block].erase(s[block].end()-(sz[block]-i));
break;
}
sz[block]--;
}
int update(int pos, int val){
if(asked%BLOK==0){
init(n,l,arr);
asked=0;
}
asked++;
poz(where[pos],mp(arr[pos],pos));
build(where[pos]);
arr[pos]=val;
for(int i=0;i+1<cur;i++)
if(s[i+1].size() and s[i+1][0].ff>val){
s[i].pb(mp(val,pos));
where[pos]=i;
sz[i]++;build(i);
return query();
}
s[cur-1].pb(mp(val,pos));where[pos]=cur-1;
sz[cur-1]++;build(cur-1);
return query();
}
