#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int SQ = 20;
int n, l;
int currentUpdate = 0;
vector<vi> difX;
vector<vii> dp;
vi a, b;
void updateComp(int c) {
int m = difX[c].size();
dp[c].clear();
dp[c].resize(m);
int ub=m-1;
REV(lb,0,m) {
while(difX[c][ub] - difX[c][lb] > l) ub--;
if(ub == m-1) {
dp[c][lb] = {1,difX[c][lb]+l};
} else {
dp[c][lb] = dp[c][ub+1];
dp[c][lb].fi++;
}
}
}
void updateAll() {
difX.clear();
b = a;
sort(all(b));
int cc = -1;
RE(i,n) {
if(i%SQ == 0) cc++, difX.pb({}), dp.pb({});
difX[cc].pb(b[i]);
}
RE(i,cc+1) updateComp(i);
}
int getCurrent() {
int m = difX.size();
int lastX = -1;
int res = 0;
RE(i,m) {
int j = upper_bound(all(difX[i]),lastX) - difX[i].begin();
if(j == difX[i].size()) continue;
res += dp[i][j].fi;
lastX = dp[i][j].se;
}
return res;
}
void removeX(int x) {
int m = difX.size();
RE(i,m) {
if(difX[i][0] <= x && x <= difX[i].back()) {
difX[i].erase(find(all(difX[i]), x));
updateComp(i);
break;
}
}
}
void insertX(int x) {
int m = difX.size();
REV(i,0,m) {
if(i == 0 || x >= difX[i].back()) {
difX[i].insert(upper_bound(all(difX[i]),x), x);
updateComp(i);
break;
}
}
}
void init(int N, int L, int X[]) {
n = N; l = L;
RE(i,n) a.pb(X[i]);
}
int update(int i, int y) {
removeX(a[i]);
a[i] = y;
insertX(a[i]);
if(currentUpdate % SQ == 0) updateAll();
currentUpdate++;
return getCurrent();
}
