#pragma GCC optimize("O3")
#include "elephants.h"
#include <string.h>
#define N 150000
#define LN 17 /* LN = floor(log2(N)) */
#define K 256
#define INF 0x3f3f3f3f
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N * 2], ii[N], n, d;
int compare(int i, int j) { return xx[i] != xx[j] ? xx[i] - xx[j] : i - j; }
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) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
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 pp[N + 1][LN + 1], jump[N], ii_[K * 2], k, k1;
void build() {
static int ii1[N];
int n_, n1, k_, g, i, j, l;
n_ = 0;
for (i = 0; i < n; i++)
if (xx[n + ii[i]] == -1)
ii[n_++] = ii[i];
k_ = 0;
for (g = 0; g < k; g++)
if (ii_[g] >= n)
xx[ii_[g] - n] = xx[ii_[g]], xx[ii_[g]] = -1, ii_[k_++] = ii_[g] - n;
i = 0, j = 0, n1 = 0;
while (i < n_ || j < k_)
ii1[n1++] = i < n_ && (j == k_ || compare(ii[i], ii_[j]) < 0) ? ii[i++] : ii_[j++];
memcpy(ii, ii1, n * sizeof *ii1);
for (i = 0, j = 0; i < n; i++) {
while (j < n && xx[ii[j]] - xx[ii[i]] <= d)
j++;
pp[i][0] = j;
}
pp[n][0] = n;
for (i = n; i >= 0; i--)
for (l = 1, j = pp[i][0]; l <= LN; l++)
j = pp[i][l] = pp[j][l - 1];
k = 0;
}
void init(int n_, int d_, int *xx_) {
int i;
n = n_, d = d_;
for (i = 0; i < n; i++)
ii[i] = i;
sort(ii, 0, n);
memcpy(xx, xx_, n * sizeof *xx_), memset(xx + n, -1, n * sizeof *xx);
build();
}
void bubble(int i) {
int g, tmp;
for (g = 0; g < k; g++)
if (ii_[g] == i)
break;
while (g > 0 && compare(ii_[g], ii_[g - 1]) < 0)
tmp = ii_[g], ii_[g] = ii_[g - 1], ii_[g - 1] = tmp, g--;
while (g + 1 < k && compare(ii_[g], ii_[g + 1]) > 0)
tmp = ii_[g], ii_[g] = ii_[g + 1], ii_[g + 1] = tmp, g++;
}
int solve() {
int g, x, h, h_, l, ans;
ans = 0;
for (g = 0, x = -INF, h = 0; g < k; g++) {
int i_ = ii_[g];
if (h < n && (xx[ii[h]] < xx[i_] || xx[ii[h]] == xx[i_] && ii[h] < i_)) {
for (l = LN; l >= 0; l--) {
h_ = pp[h][l];
if (h_ < n && (xx[ii[h_]] < xx[i_] || xx[ii[h_]] == xx[i_] && ii[h_] < i_))
ans += 1 << l, h = h_;
}
ans++, x = xx[ii[h]], h = pp[h][0];
}
if (xx[i_] - x <= d)
continue;
if (i_ < n)
h++;
else
ans++, x = xx[i_], h = jump[i_ - n];
}
if (h < n) {
for (l = LN; l >= 0; l--)
if (pp[h][l] < n)
ans += 1 << l, h = pp[h][l];
ans++;
}
return ans;
}
int update(int i, int y) {
int lower, upper;
if (k1 == K)
build(), k1 = 0;
k1++;
if (xx[n + i] == -1) {
ii_[k++] = i, bubble(i);
ii_[k++] = n + i, xx[n + i] = y, bubble(n + i);
} else
xx[n + i] = y, bubble(n + i);
lower = -1, upper = n;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (xx[ii[h]] - xx[n + i] <= d)
lower = h;
else
upper = h;
}
jump[i] = upper;
return solve();
}
