#include <bits/stdc++.h>
#include "elephants.h"
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
int n, Len;
const int K = 400;
int block[K][2 * K], nxt[K][2 * K], val[K][2 * K], sz[K], b[(int) 2e5+5], a[(int) 2e5+5];
pair<int, int> go[K][2 * K];
void make(int i) {
int R = 0;
for (int L = 0; L < sz[i]; ++L) {
while (R < sz[i] && block[i][R] - block[i][L] <= Len) ++R;
nxt[i][L] = R;
val[i][L] = block[i][L] + Len;
}
for (int j = sz[i] - 1; j >= 0; --j) {
if (nxt[i][j] == sz[i]) {
go[i][j] = {1, val[i][j]};
}
else {
go[i][j] = {go[i][nxt[i][j]].first + 1, go[i][nxt[i][j]].second};
}
}
}
void build() {
n = 0;
for (int i = 0; i < K; i++)
for (int j = 0; j < sz[i]; j++) b[n++] = block[i][j];
for (int i = 0; i < n; i += K) {
int r = min(n, i + K);
sz[i / K] = r - i;
for (int j = 0; j < r; j++) block[i / K][j] = b[i + j];
make(i / K);
}
}
void init(int N, int _L, int X[]) {
n = N, Len = _L;
for (int i = 0; i < n; i++) b[i] = a[i] = X[i];
for (int i = 0; i < n; i += K) {
int r = min(n, i + K);
sz[i / K] = r - i;
for (int j = 0; j < r; j++) block[i / K][j] = b[i + j];
}
build();
}
void erase(int i, int x) {
for (int j = 0; j < sz[i]; j++) {
if (block[i][j] < x) continue;
block[i][j] = block[i][j + 1];
}
sz[i]--;
make(i);
}
void del(int x) {
for (int i = 0; i < K; i++) {
if (x <= block[i][sz[i] - 1]) {
erase(i, x);
break;
}
}
}
void add(int i, int x) {
int dummy = x;
for (int j = 0; j < sz[i]; j++) {
if (block[i][j] < x) continue;
swap(block[i][j], dummy);
}
block[i][sz[i]++] = dummy;
make(i);
}
void Update(int x) {
for (int i = 0; i < K; i++) {
if (x <= block[i][sz[i] - 1]) {
add(i, x);
break;
}
if (i == (n - 1) / K) {
add(i, x);
break;
}
}
}
int q = 0;
int update(int x, int y) {
del(a[x]);
a[x] = y;
Update(a[x]);
q++;
if (q == K) {
build();
q = 0;
}
int ans = 0, pos = block[0][0], i = 0, j = 0;
int cnt = 0;
while (sz[i]) {
ans += go[i][j].first;
pos = go[i][j].second;
while (sz[i] && block[i][sz[i] - 1] <= pos) i++;
if (!sz[i]) break;
int l = 0, r = sz[i] - 1;
while (l < r) {
int m = (l + r) / 2;
if (block[i][m] <= pos) l = m + 1;
else r = m;
}
j = r;
}
return ans;
}
