/* upsolve after reading solution */
#include "elephants.h"
#include <string.h>
#define N 150000
#define K 500
#define M 300
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N], ii[N], hh[N], n, d;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (xx[ii[j]] == xx[i_])
j++;
else if (xx[ii[j]] < xx[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int iii[M][K * 2], cnt[M][K * 2], xx_[M][K * 2], kk[M], m;
void build(int h) {
int i, j;
for (i = kk[h] - 1, j = kk[h]; i >= 0; i--) {
int x = xx[iii[h][i]];
while (xx[iii[h][j - 1]] - x > d)
j--;
if (j == kk[h])
cnt[h][i] = 1, xx_[h][i] = x;
else
cnt[h][i] = cnt[h][j] + 1, xx_[h][i] = xx_[h][j];
}
}
void build_() {
int h, i;
for (h = 0; h < m; h++) {
int l = h * K, r = min((h + 1) * K, n);
kk[h] = r - l;
for (i = l; i < r; i++)
iii[h][i - l] = ii[i], hh[ii[i]] = h;
build(h);
}
}
void extract() {
int h, h_, i;
for (h = 0, h_ = 0; h < m; h++)
for (i = 0; i < kk[h]; i++)
ii[h_++] = iii[h][i];
}
void init(int n_, int d_, int *xx_) {
int i;
n = n_, d = d_, memcpy(xx, xx_, n * sizeof *xx_);
for (i = 0; i < n; i++)
ii[i] = i;
sort(ii, 0, n);
m = (n + K - 1) / K;
build_();
}
int k;
void remove_(int i_) {
int h, i;
h = hh[i_];
for (i = 0; i < kk[h]; i++)
if (iii[h][i] == i_) {
kk[h]--;
while (i < kk[h])
iii[h][i] = iii[h][i + 1], i++;
}
build(h);
}
void add(int i_) {
int h, i;
for (h = 0; h < m; h++)
if (kk[h] && xx[iii[h][0]] > xx[i_]) {
if (h == 0)
h++;
break;
}
h--;
kk[h]++;
for (i = kk[h] - 1; i > 0 && xx[i_] < xx[iii[h][i - 1]]; i--)
iii[h][i] = iii[h][i - 1];
iii[h][i] = i_, hh[i_] = h;
build(h);
}
int solve() {
int h, x, ans;
x = -INF, ans = 0;
for (h = 0; h < m; h++)
if (kk[h] && xx[iii[h][kk[h] - 1]] - x > d) {
int lower = -1, upper = kk[h] - 1, i;
while (upper - lower > 1) {
i = (lower + upper) / 2;
if (xx[iii[h][i]] - x <= d)
lower = i;
else
upper = i;
}
i = upper;
ans += cnt[h][i], x = xx_[h][i];
}
return ans;
}
int update(int i, int x) {
if (k == K)
extract(), build_(), k = 0;
remove_(i), xx[i] = x, add(i), k++;
return solve();
}
