#include "elephants.h"
#include <string.h>
#define N 150000
#define LN 17 /* LN = floor(log2(N)) */
#define K 64
#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[LN + 1][N + 1], ii_[K * 2], k;
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[0][i] = j;
}
pp[0][n] = n;
for (l = 1; l <= LN; l++)
for (i = 0; i <= n; i++)
pp[l][i] = pp[l - 1][pp[l - 1][i]];
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, l, ans;
ans = 0;
for (g = 0, x = -INF, h = 0; g < k; g++) {
int i_ = ii_[g];
if (h < n && compare(ii[h], i_) < 0) {
for (l = LN; l >= 0; l--)
if (pp[l][h] < n && compare(ii[pp[l][h]], i_) < 0)
ans += 1 << l, h = pp[l][h];
ans++, x = xx[ii[h]], h = pp[0][h];
}
if (xx[i_] - x <= d)
continue;
if (i_ < n)
h++;
else {
ans++, x = xx[i_];
if (h < n && xx[ii[h]] - x <= d) {
for (l = LN; l >= 0; l--)
if (h + (1 << l) < n && xx[ii[h + (1 << l)]] - x <= d)
h += 1 << l;
h++;
}
}
}
if (h < n) {
for (l = LN; l >= 0; l--)
if (pp[l][h] < n)
ans += 1 << l, h = pp[l][h];
ans++;
}
return ans;
}
int update(int i, int y) {
if (xx[n + i] == -1) {
if (k == K * 2)
build();
ii_[k++] = i, bubble(i);
ii_[k++] = n + i, xx[n + i] = y, bubble(n + i);
} else
xx[n + i] = y, bubble(n + i);
return solve();
}
