#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
const int MAXN = 150005;
int suf[MAXN], x[MAXN], extra[MAXN], marc[MAXN], n, tam = 1250, l, cur;
set<pair<int,int>> st;
vector< vector< pair<int,int> > > buckets;
void fazbucket(int i){
int lst = buckets[i].size()-1;
for(int j = buckets[i].size()-1; j >= 0; j--){
while(buckets[i][lst].fi - buckets[i][j].fi > l)lst--;
if(lst+1 < buckets[i].size()){
suf[ buckets[i][j].sc ] = suf[ buckets[i][lst+1].sc ] + 1;
extra[ buckets[i][j].sc ] = extra[ buckets[i][lst+1].sc ];
}else{
suf[ buckets[i][j].sc ] = 1;
extra[ buckets[i][j].sc ] = buckets[i][j].fi + l;
}
}
}
void faz(){
auto it = st.rbegin();
buckets.clear();
int qtd = 0, b = 0; buckets.push_back({});
while(it != st.rend()){
if(qtd == tam){
reverse(buckets[b].begin(),buckets[b].end());
fazbucket(b);
buckets.push_back({});
qtd = 0; b++;
}
qtd++;
marc[it->sc] = b;
buckets[b].push_back(*it);
it++;
}
reverse(buckets[b].begin(),buckets[b].end());
fazbucket(b);
}
void init(int N, int L, int X[])
{
n = N; l = L;
for(int i = 0; i < n; i++){
st.insert({X[i],i});
x[i] = X[i];
}
faz();
}
int update(int i, int y)
{
cur++;
if(cur == 387){
st.erase({x[i],i});
x[i] = y;
st.insert({x[i],i});
cur = 0;
faz();
}else{
st.erase({x[i],i});
for(int j = 0; j < buckets[ marc[i] ].size(); j++)
if(buckets[ marc[i] ][j].fi == x[i]){ buckets[ marc[i] ].erase(buckets[marc[i]].begin()+j); break; }
fazbucket(marc[i]);
x[i] = y;
st.insert({x[i],i});
marc[i] = buckets.size()-1;
for(int j = 0; j < buckets.size(); j++)
if(buckets[j][0].fi <= x[i]){ marc[i] = j; break; }
for(int j = buckets[ marc[i] ].size()-1; j >= -1; j--){
if(j == -1)buckets[ marc[i] ].insert(buckets[marc[i]].begin()+j+1, {x[i],i} );
else if(buckets[ marc[i] ][j].fi < x[i]){ buckets[ marc[i] ].insert(buckets[marc[i]].begin()+j+1, {x[i],i} ); break; }
}
fazbucket(marc[i]);
}
int ii = st.begin()->sc, ans = 0;
while(1){
ans += suf[ii];
auto it = st.upper_bound({extra[ii], 100000000});
if(it == st.end())break;
ii = it->sc;
}
return ans;
}
