#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int M = 150005;
int B = 450;
int n,ll;
int a[M];
int t[M];
int fix[M];
pair<int,int> pos[M];
set<pair<int,int>> s;
vector <vector<pair<int,int>>> v(605);
pair <int,int> nxt[M];
int nb = (n-1+B-1)/B;
int op;
void calc(int j) {
if (v[j].empty()) return;
int r = v[j].size()-1;
for (int i = v[j].size()-1; i >= 0; i--) {
int cur = v[j][i].first + ll;
while (r > i && v[j][r].first > cur) r--;
if (r == v[j].size()-1) {
nxt[v[j][i].second] = {1,cur};
continue;
}
nxt[v[j][i].second] = {nxt[v[j][r+1].second].first+1,nxt[v[j][r+1].second].second};
}
}
void solve() {
int cur = 0;
for (int i = 0; i <= 500; i++) {
for (auto p:v[i]) pos[cur++] = p;
v[i].clear();
}
for (int i = 0; i < n; i++) {
v[i/B].push_back(pos[i]);
fix[pos[i].second] = i/B;
}
nb = (n + B - 1) / B;
for (int i = 0; i < nb; i++) {
calc(i);
}
op = 0;
}
int getans() {
int cur = -1;
int res = 0;
int id = 0;
while (id < nb) {
if (v[id].empty() || v[id].back().first <= cur) {
id++;
continue;
}
auto it = upper_bound(v[id].begin(),v[id].end(),make_pair(cur,INT_MAX));
int ind = (*it).second;
res += nxt[ind].first;
cur = nxt[ind].second;
id = fix[ind];
}
return res;
}
void remove(int x) {
pair<int,int> res = {a[x],x};
int j = fix[x];
auto it = lower_bound(v[j].begin(), v[j].end(), make_pair(a[x], x));
if (it != v[j].end() && (*it).second == x) v[j].erase(it);
calc(j);
}
void add(int x, int pos) {
a[x] = pos;
int j = max(0, nb - 1);
for (int i = 0; i < nb - 1; i++) {
if (!v[i].empty() && pos <= v[i].back().first) {
j = i;
break;
}
}
auto it = lower_bound(v[j].begin(),v[j].end(),make_pair(a[x],x));
v[j].insert(it,{a[x],x});
fix[x] = j;
calc(j);
if (++op>=B) {
solve();
return;
}
}
void init(int N, int L, int X[]) {
n = N; ll = L;
nb = 1;
for (int i = 0; i < n; i++) {
a[i] = X[i];
v[0].push_back({X[i],i});
}
sort(v[0].begin(),v[0].end());
solve();
}
int update(int i, int y) {
remove(i);
add(i,y);
int res = getans();
return res;
}
