#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
int n, L;
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 k) {
int r = 0;
for (int i = 0; i < sz[k]; i++) {
while (r < sz[k] && block[k][r] - block[k][i] <= L) r++;
nxt[k][i] = r;
val[k][i] = block[k][i] + L;
}
for (int i = sz[k] - 1; i >= 0; i--) {
if (nxt[k][i] == sz[k]) go[k][i] = {1, val[k][i]};
else go[k][i] = {1 + go[k][nxt[k][i]].first, go[k][nxt[k][i]].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 = i; j < r; j++) block[i / K][j - i] = b[j];
make(i / K);
}
}
void init(int N, int _L, int X[]) {
n = N, L = _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 = i; j < r; j++) block[i / K][j - i] = b[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;
}
