/* upsolve using LCT */
#include "elephants.h"
#define N 150000
#define Q 150000
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N * 2], 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 zz[1 + N * 2], ll[1 + N * 2], rr[1 + N * 2], ii[1 + N * 2], u_, l_, r_;
int node(int i) {
static int _ = 1;
zz[_] = rand_(), ii[_] = i;
return _++;
}
int first(int u) {
return ll[u] == 0 ? u : first(ll[u]);
}
int last(int u) {
return rr[u] == 0 ? u : last(rr[u]);
}
void split(int u, int i) {
int c;
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
c = compare(ii[u], i);
if (c < 0) {
split(rr[u], i);
rr[u] = l_, l_ = u;
} else if (c > 0) {
split(ll[u], i);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
int tt[1 + N * 2][2], pp[1 + N * 2], sz[1 + N * 2];
int dir(int u) {
return tt[pp[u]][0] != u;
}
int is_root(int u) {
return tt[pp[u]][0] != u && tt[pp[u]][1] != u;
}
void pul(int u) {
int l = tt[u][0], r = tt[u][1];
sz[u] = sz[l] + sz[r] + (u <= n);
}
void attach(int p, int u, int d) {
if (p)
tt[p][d] = u, pul(p);
if (u)
pp[u] = p;
}
void rotate(int u) {
int v = pp[u], w = pp[v], du = dir(u), dv = dir(v);
if (is_root(v))
pp[u] = w;
else
attach(w, u, dv);
attach(v, tt[u][du ^ 1], du);
attach(u, v, du ^ 1);
}
void splay(int u) {
while (!is_root(u)) {
int v = pp[u];
if (!is_root(v))
rotate(dir(u) == dir(v) ? v : u);
rotate(u);
}
}
void expose(int u) {
int v, w;
for (w = 0, v = u; v; w = v, v = pp[v])
splay(v), attach(v, w, 1);
splay(u);
}
void link(int u, int v) {
expose(u), expose(v), attach(v, u, 1);
}
void cut(int u) {
expose(u);
pp[tt[u][0]] = 0, attach(u, 0, 0);
}
int depth(int u) {
expose(u);
return sz[u];
}
void init(int n_, int d_, int *xx_) {
static int ii[N * 2];
int i;
n = n_, d = d_;
for (i = 0; i < n; i++)
xx[i] = xx_[i], xx[n + i] = xx[i] + d;
for (i = 0; i < n * 2; i++)
ii[i] = i;
sort(ii, 0, n * 2);
for (i = 1; i <= n; i++)
sz[i] = 1;
for (i = 0; i < n * 2; i++) {
if (i + 1 < n * 2)
link(1 + ii[i], 1 + (ii[i] < n ? ii[i] + n : ii[i + 1]));
u_ = merge(u_, node(ii[i]));
}
}
int update(int i, int x) {
int u, v, p;
split(u_, n + i), v = u_, p = l_ ? ii[last(l_)] : -1;
if (p >= n) {
cut(1 + p);
if (r_)
link(1 + p, 1 + ii[first(r_)]);
}
cut(1 + n + i);
u_ = merge(l_, r_);
split(u_, i), u = u_, p = l_ ? ii[last(l_)] : -1;
if (p >= n) {
cut(1 + p);
if (r_)
link(1 + p, 1 + ii[first(r_)]);
}
u_ = merge(l_, r_);
xx[i] = x, xx[n + i] = xx[i] + d;
split(u_, n + i), p = l_ ? ii[last(l_)] : -1;
if (p >= n)
cut(1 + p), link(1 + p, 1 + n + i);
if (r_)
link(1 + n + i, 1 + ii[first(r_)]);
u_ = merge(merge(l_, v), r_);
split(u_, i), p = l_ ? ii[last(l_)] : -1;
if (p >= n)
cut(1 + p), link(1 + p, 1 + i);
u_ = merge(merge(l_, u), r_);
return depth(1 + ii[first(u_)]);
}
