// NOTE: 0-indexed
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include "camera.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define fir first
#define sec second
#define lb lower_bound
#define ub upper_bound
const int N = 2e5 + 5, PS = 1e9;
int n, l;
int sq1, sq2;
arr<int, N> ps;
map<int, int> at;
vec<pii> rng;
vec<set<int>> lst;
map<int, pii> jmp;
void cmp(int id) {
for (auto it = jmp.lb(rng[id].fir); it != jmp.end() && it->fir <= rng[id].sec;) it = jmp.erase(it);
for (auto it = lst[id].rbegin(); it != lst[id].rend(); it++) {
int x = *it;
auto nx = lst[id].ub(x + l);
if (nx == lst[id].end()) jmp[x] = {1, x + l};
else jmp[x] = {jmp[*nx].fir + 1, jmp[*nx].sec};
}
}
void bld() {
rng.clear(), lst.clear(), jmp.clear();
pii cr_rng = {0, 0}; set<int> cr_lst;
for (pii x : at) {
cr_rng.sec = x.fir, cr_lst.insert(x.fir);
if (cr_lst.size() >= sq1) {
rng.pb(cr_rng), lst.pb(cr_lst);
cr_rng = {cr_rng.sec + 1, cr_rng.sec + 1}, cr_lst.clear();
}
}
cr_rng.sec = PS;
rng.pb(cr_rng), lst.pb(cr_lst);
for (int i = 0; i < rng.size(); i++) cmp(i);
// cout << "SQRT: " << sq << '\n';
// for (pii x : rng)
// cout << x.fir << " " << x.sec << '\n';
// for (pair<int, pii> x : jmp) {
// cout << x.fir << ": " << x.sec.fir << " " << x.sec.sec << '\n';
// }
}
void init(int _n, int _l, int _ps[]) {
n = _n, l = _l; assert(n <= 70000);
if (n <= 50000) {
sq1 = 150, sq2 = 500;
} else {
sq1 = 200, sq2 = 800;
}
for (int i = 1; i <= n; i++) ps[i] = _ps[i - 1];
for (int i = 1; i <= n; i++) at[ps[i]]++;
bld();
}
int rsp() {
int ans = 0, prv = -1;
for (int i = 0; i < rng.size(); i++) {
auto it = lst[i].ub(prv);
if (it == lst[i].end()) continue;
ans += jmp[*it].fir, prv = jmp[*it].sec;
}
return ans;
}
int fnd(int x) {
for (int i = 0; i < rng.size(); i++)
if (rng[i].fir <= x && x <= rng[i].sec) return i;
assert(false); return -1;
}
int cnt;
int update(int i, int nw_ps) {
i++;
int j = fnd(ps[i]), k = fnd(nw_ps);
at[ps[i]]--; if (at[ps[i]] == 0) at.erase(ps[i]), lst[j].erase(ps[i]);
at[nw_ps]++; lst[k].insert(nw_ps);
ps[i] = nw_ps;
cmp(j), cmp(k);
int ans = rsp();
cnt++;
if (cnt >= sq2)
bld(), cnt = 0;
return ans;
}
