#include "elephants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int MAXN = 1.5e5+10;
const int B = 400;
int N,L,Bcnt;
vector<int> pos[MAXN];
int arr[MAXN];
int in[MAXN];
vector<pair<int,int>> dp[MAXN];
void solve(int id){
vector<int> &poss = pos[id];
vector<pair<int,int>> &dps = dp[id];
int sz = poss.size();
dps.resize(sz);
int cur = sz;
for(int i = sz-1;i>=0;--i){
while(poss[cur-1] > poss[i]+L) --cur;
if(cur == sz){
dps[i].ff = 1;
dps[i].ss = poss[i];
}
else{
dps[i].ff = dps[cur].ff+1;
dps[i].ss = dps[cur].ss;
}
}
}
int query(){
int ans = dp[0][0].ff, lst = dp[0][0].ss;
for(int i = 1;i<Bcnt;++i){
if(pos[i].back() > lst+L){
int it = upper_bound(pos[i].begin(),pos[i].end(),lst+L)-pos[i].begin();
ans += dp[i][it].ff; lst = dp[i][it].ss;
}
}
//cout << dp[0][0].ff << "\n";
return ans;
}
void unite(){
for(int i = 0;i<Bcnt-1;++i){
if(pos[i].size()+pos[i+1].size() < 2*B){
pos[i].insert(pos[i].end(),pos[i+1].begin(),pos[i+1].end());
pos[i+1].clear(); dp[i+1].clear();
for(int j = i+2;j<Bcnt;++j){
swap(pos[j-1],pos[j]);
swap(dp[j-1],dp[j]);
}
--Bcnt;
solve(i);
unite();
return;
}
}
}
void del(int tar){
int id = 0;
while(pos[id].back() < tar){
++id;
}
pos[id].erase(lower_bound(pos[id].begin(),pos[id].end(),tar));
if(pos[id].empty()){
for(int i = id+1;i<Bcnt;++i){
swap(pos[i-1],pos[i]);
swap(dp[i-1],dp[i]);
}
--Bcnt;
}
else{
solve(id);
}
unite();
}
void upd(int tar){
int id = 0;
while(id < Bcnt-1 && pos[id].back() < tar) ++id;
pos[id].insert(upper_bound(pos[id].begin(),pos[id].end(),tar),tar);
/*for(auto x : pos[id]){
cout << x << " ";
}
cout << "\n";*/
if(pos[id].size() == 2*B){
for(int i = Bcnt-1;i>id;--i){
swap(pos[i+1],pos[i]);
swap(dp[i+1],dp[i]);
}
pos[id+1].insert(pos[id+1].begin(),pos[id].begin()+B,pos[id].end());
pos[id].erase(pos[id].begin()+B,pos[id].end());
++Bcnt;
solve(id); solve(id+1);
}
else{
solve(id);
}
unite();
}
void init(int n,int l, int X[]){
N = n; L = l;
Bcnt = (N-1)/B+1;
for(int i = 0;i<N;++i){
arr[i] = X[i];
pos[i/B].push_back(arr[i]);
}
for(int i = 0;i<Bcnt;++i){
solve(i);
}
}
int update(int i, int val){
del(arr[i]);
arr[i] = val;
upd(val);
int ans = query();
return ans;
}
