#include "elephants.h"
#include "bits/stdc++.h"
#define MAXN 150009
#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=1000;
vector<PII>dp[MAXN/BLOK+3],s[MAXN/BLOK+3];
void build(int block){
int p=sz[block]-1;
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);
else dp[block][i]=mp(0,i);
}
}
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[]){
n = N; l = L;
if(asked){
for(int i=0;i<n;i++){
arr[i]=X[i];
tmp[i]=mp(X[i],i);
}
}
else{
int pos=0;
for(int i=0;i<cur;i++){
tr(it,s[i])
tmp[pos++]=*it;
s[i].clear();sz[i]=0;
}
}
cur=0;
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++){
dp[i].resize(sz[i]);
build(i);
}
}
void rem(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]--;dp[block].ppb();
build(block);
}
void add(int block){
sz[block]++;dp[block].pb(mp(-1,-1));
for(int i=sz[block]-1;i>0;i--)
if(s[block][i].ff<s[block][i-1].ff)
swap(s[block][i],s[block][i-1]);
build(block);
}
int update(int pos, int val){
if(asked%BLOK==0){
asked=0;
init(n,l,arr);
}asked++;
rem(where[pos],mp(arr[pos],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;add(i);
return query();
}
s[cur-1].pb(mp(val,pos));where[pos]=cur-1;add(cur-1);
return query();
}
