#include "elephants.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Pi acos(-1);
#define mod 1e9+7
#define inf 1e18
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
const int NN = 2e5+5;
const int B = 700;
int n, a[NN], l, cur;
int sz[NN], bb[NN], asked;
pii tmp[NN];
vpii dp[B], s[B];
void build(int b){
int last = sz[b] -1;
for(int i=sz[b]-1;i>=0;i--){
while(s[b][i].ff +l < s[b][last].ff && last >= i) last--;
if(last < sz[b]-1) dp[b][i] = {dp[b][last+1].ff+1, dp[b][last+1].ss};
else dp[b][i] = {0, i};
}
}
void init(int N, int L, int X[]){
n = N, l = L;
for(int i=0;i<cur;i++){
s[i].clear();
sz[i] = 0;
}
for(int i=0;i<n;i++){
tmp[i] = {X[i], i};
a[i] = X[i];
}
sort(tmp, tmp+n);
cur = 0;
for(int i=0;i<n;i++){
bb[tmp[i].ss] = cur;
s[cur].pb(tmp[i]);
sz[cur]++;
if(sz[cur] == B) cur++;
}
if(sz[cur]) cur++;
for(int i=0;i<cur;i++){
dp[i].resize(sz[i]);
build(i);
}
}
void rem(int b, pii val){
auto err = lb(all(s[b]), val);
s[b].erase(err);
sz[b]--;
dp[b].resize(sz[b]);
build(b);
}
void sett(int b, pii val){
s[b].pb(val);
sz[b]++;
dp[b].resize(sz[b]);
bb[val.ss] = b;
int i = sz[b]-1;
while(i > 0 && s[b][i].ff < s[b][i-1].ff) { swap(s[b][i], s[b][i-1]); i--; }
build(b);
}
int qq(){
int last = -1, ans = 0;
for(int i=0;i<cur;i++){
if(sz[i]){
auto pp = ub(all(s[i]), (pii)mp(last, mod)) - s[i].begin();
if(pp < sz[i]){
if(dp[i][pp].ff) ans += dp[i][pp].ff, pp = dp[i][pp].ss;
last = s[i][pp].ff+l, ans++;
}
}
}return ans;
}
int update(int i, int nw){
if(asked && asked%B == 0) { init(n, l, a); asked = 0; }
asked++;
rem(bb[i], mp(a[i], i));
a[i] = nw;
for(int b = 0; b+1 < cur; b++){
if(sz[b+1] && s[b+1][0].ff > nw){
sett(b, {a[i], i});
int ans = qq();
return ans;
}
}
sett(cur-1, {a[i], i});
int ans = qq();
return ans;
}
