#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#define ull unsigned long long
const int mxn = 150000, sq = 400;
int n, qq = 0, l;
int x[mxn + 1], mx[mxn + 1], cnt[mxn + 1], block[mxn + 1];
vt<pii>comp[mxn + 1];
void build(int s){
int r = sz(comp[s]);
for(int i = sz(comp[s]) - 1; i >= 0; i--){
while(r > 0 && comp[s][i].fi + l < comp[s][r - 1].fi)r--;
if(r == sz(comp[s])){
cnt[comp[s][i].se] = 1; mx[comp[s][i].se] = comp[s][i].fi + l;
}else{
cnt[comp[s][i].se] = cnt[comp[s][r].se] + 1; mx[comp[s][i].se] = mx[comp[s][r].se];
}
}
}
void solve(){
for(int i = 0; i < n; i++){
block[i] = i / sq;
comp[i / sq].pb(mpp(x[i], i));
}
for(int i = 0; i <= (n - 1) / sq; i++)build(i);
}
void init(int N, int L, int X[])
{
n = N; l = L;
for(int i = 0; i < n; i++)x[i] = X[i];
solve();
}
int getblock(int x){
for(int i = (n - 1) / sq; i >= 0; i--){
if(sz(comp[i]) == 0)continue;
if(comp[i][0].fi <= x)return(i);
}
return(0);
}
void rebuild(){
vt<pii>all;
for(int i = 0; i <= (n - 1) / sq; i++){
for(auto j: comp[i])all.pb(j);
comp[i].clear();
}
for(int i = 0; i <= n - 1; i++){
block[all[i].se] = i / sq;
comp[i / sq].pb(all[i]);
}
for(int i = 0; i <= (n - 1) / sq; i++)build(i);
}
int update(int id, int y)
{
int bl = block[id];
for(int i = 0; i < sz(comp[bl]); i++){
if(comp[bl][i].se == id){
comp[bl].erase(comp[bl].begin() + i);
break;
}
}
build(bl);
x[id] = y;
int br = getblock(x[id]), pos = sz(comp[br]); block[id] = br;
for(int i = 0; i < sz(comp[br]); i++){
if(comp[br][i].fi > y){
pos = i;
break;
}
}
comp[br].insert(comp[br].begin() + pos, mpp(x[id], id));
build(br);
int position = -1, camera = 0;
for(int i = 0; i <= (n - 1) / sq; i++){
if(sz(comp[i]) == 0)continue;
int id = lower_bound(ALL(comp[i]), mpp(position + 1, -1)) - comp[i].begin();
if(id == sz(comp[i]))continue;
else{
camera += cnt[comp[i][id].se]; position = mx[comp[i][id].se];
}
}
++qq;
if(qq == sq){
rebuild(); qq = 0;
}
return(camera);
}
/*
#define MAX_N 1000000
#define MAX_M 1000000
static int N,L,M;
static int X[MAX_N];
static int ii[MAX_M];
static int yy[MAX_M];
static int sol[MAX_M];
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&L,&M));
for(i=0; i<N; i++)
my_assert(1==scanf("%d",&X[i]));
for(i=0; i<M; i++)
my_assert(3==scanf("%d %d %d",&ii[i],&yy[i],&sol[i]));
}
int main()
{
int i, ans;
read_input();
init(N,L,X);
for(i=0; i<M; i++) {
ans = update(ii[i],yy[i]);
cout << ans << "\n";
}
printf("Correct.\n");
return 0;
}
*/
