#include <bits/stdc++.h>
#include "elephants.h"
#define all(v) begin(v), end(v)
using namespace std;
int n, l;
using ll = long long;
const ll INF = (ll)1e18 + 10;
const int inf = 1e9 + 10;
const int maxn = 2e5 + 5;
int pos[maxn];
struct block {
int n = 0;
vector<ll> x = {}, last = {}, dp = {};
block() {};
void rebuild() {
x.push_back(INF);
last.assign(n + 1, -1);
dp.assign(n + 1, 0);
int j = n;
for (int i = n - 1; i >= 0; --i) {
while (j > 0 && x[i] + l < x[j - 1]) j--;
last[i] = (j == n ? x[i] : last[j]);
dp[i] = dp[j] + 1;
}
x.pop_back();
last.pop_back();
dp.pop_back();
}
void insert(int y) {
auto it = lower_bound(all(x), y);
x.insert(it, y);
n++;
rebuild();
}
void erase(int y) {
auto it = lower_bound(all(x), y);
x.erase(it);
n--;
rebuild();
}
};
const int B = 400;
block b[maxn / B + 10];
int P;
void init(int N, int L, int X[]) {
n = N;
l = L;
P = (n - 1) / B + 1;
for (int i = 0; i < n; ++i) {
pos[i] = X[i];
b[i / B].insert(pos[i]);
}
}
int it = 0;
int update(int i, int y) {
int bl = 0;
for (int cur = 0; cur < P; ++cur) {
if (b[cur].n != 0) {
bl = cur;
if (b[cur].x.back() >= pos[i]) {
break;
}
}
}
b[bl].erase(pos[i]);
pos[i] = y;
bl = 0;
for (int cur = 0; cur < P; ++cur) {
if (b[cur].n != 0) {
bl = cur;
if (b[cur].x.back() >= pos[i]) {
break;
}
}
}
b[bl].insert(pos[i]);
ll res = 0, last = -INF;
for (int bl = 0; bl < P; ++bl) {
if (b[bl].n == 0) continue;;
int i = upper_bound(all(b[bl].x), last + l) - b[bl].x.begin();
if (i >= b[bl].n) continue;
res += b[bl].dp[i];
last = b[bl].last[i];
}
if (it++ > n / B) {
for (int i = 0; i < P; ++i) {
b[i] = {};
}
vector<int> p(n);
iota(all(p), 0);
sort(all(p), [](int i, int j) { return pos[i] < pos[j]; });
for (int i = 0; i < n; ++i) {
b[i / B].insert(pos[p[i]]);
}
it = 0;
}
return res;
}
