#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;
random_device rd;
mt19937 mt(rd());
using ptr = struct Node*;
struct Node {
int pri, sz, val, agg, lazy;
ptr l, r, par;
Node (int _v) {
pri = mt();
sz = 1;
l = r = par = 0;
val = agg = _v;
lazy = 0;
}
};
inline int sz(ptr n) { return n ? n->sz : 0; }
inline int agg(ptr n) { return n ? n->agg : -1; }
void push(ptr n) {
if (!n) return;
n->val += n->lazy;
n->agg += n->lazy;
if (n->l) n->l->lazy += n->lazy;
if (n->r) n->r->lazy += n->lazy;
n->lazy = 0;
}
ptr pull(ptr n) {
if (!n) return n;
push(n->l), push(n->r);
n->sz = sz(n->l) + 1 + sz(n->r);
n->agg = max({agg(n->l), n->val, agg(n->r)});
if (n->l) n->l->par = n;
if (n->r) n->r->par = n;
return n;
}
pair<ptr, ptr> spliti(ptr n, int i) {
if (!n) return {n, n};
push(n);
n->par = 0;
if (i <= sz(n->l)) {
auto [l, r] = spliti(n->l, i);
n->l = r;
return {l, pull(n)};
} else {
auto [l, r] = spliti(n->r, i - sz(n->l) - 1);
n->r = l;
return {pull(n), r};
}
}
tuple<ptr, ptr, ptr> cut(ptr n, int lo, int hi) {
auto [lhs, r] = spliti(n, hi + 1);
auto [l, m] = spliti(lhs, lo);
return {l, m, r};
}
ptr merge(ptr l, ptr r) {
if (!l || !r) return l ? l : r;
push(l), push(r);
ptr t;
if (l->pri > r->pri) l->r = merge(l->r, r), t = l;
else r->l = merge(l, r->l), t = r;
return pull(t);
}
void add(ptr n, int v) {
if (!n) return;
n->lazy += v;
push(n);
}
int order(ptr n, ptr from = 0) {
if (!n) return -1; // hack
int res = order(n->par, n);
if (from == n->r || !from) res += sz(n->l) + 1;
return res;
}
void clean(ptr n) {
if (!n) return;
clean(n->par);
push(n);
}
ll n, w;
set<pl> cows;
vt<ll> pos;
vt<pair<ptr, ptr>> loc; // {in, out}
ptr tour;
void erase(int u) {
int in = order(loc[u].f);
int out = order(loc[u].s);
auto [l, mid, r] = cut(tour, in, out);
auto [ml, m, mr] = cut(mid, 1, sz(mid) - 2);
push(ml);
add(m, -(ml->val) - 1);
tour = merge(l, r);
cows.erase({pos[u], u});
auto it = cows.lower_bound({pos[u], -INF});
int p = it->s;
clean(loc[p].f);
add(m, loc[p].f->val + 1);
auto [lhs, rhs] = spliti(tour, order(loc[p].f) + 1);
tour = merge(lhs, merge(m, rhs));
}
void insert(int u, ll x) {
pos[u] = x;
auto pit = prev(cows.lower_bound({x, -INF}));
auto it = cows.lower_bound({pit->f - w, -INF});
auto eit = cows.lower_bound({x - w, -INF});
ptr mid = 0;
auto cit = cows.lower_bound({x, -INF});
if (it->f < eit->f && ((cit->f == x && cit->s > u) || cit->f > x)) {
int in = order(loc[it->s].f);
int out = order(loc[prev(eit)->s].s);
ptr l, r;
tie(l, mid, r) = cut(tour, in, out);
tour = merge(l, r);
int op = cit->s; // original parent
clean(loc[op].f);
add(mid, -loc[op].f->val - 1);
}
pit = cows.upper_bound({x + w, INF});
int p = pit->s;
clean(loc[p].f);
int rd = loc[p].f->val + 1;
add(mid, rd + 1);
auto inn = new Node(rd);
auto outn = new Node(rd);
mid = merge(inn, merge(mid, outn));
loc[u] = {inn, outn};
auto nxt = cows.lower_bound({x, u});
int si;
if (nxt->f + w < pos[p]) si = order(loc[nxt->s].f); // before next child
else si = order(loc[p].s); // end of children
auto [lhs, rhs] = spliti(tour, si);
tour = merge(lhs, merge(mid, rhs));
cows.insert({x, u});
}
void build(int u, int d = 0) {
ptr in = new Node(d);
tour = merge(tour, in);
loc[u].f = in;
if (cows.lower_bound({pos[u], -INF})->s == u && pos[u] != -INF) {
auto pit = prev(cows.lower_bound({pos[u], -INF}));
auto it = cows.lower_bound({pit->f - w, -INF});
auto eit = cows.lower_bound({pos[u] - w, -INF});
while (it != eit) {
build(it->s, d + 1);
it++;
}
}
ptr out = new Node(d);
tour = merge(tour, out);
loc[u].s = out;
}
void init(int N, int L, int X[]) {
n = N + 2;
w = L;
pos.resize(n);
loc.resize(n);
F0R (i, n - 2) pos[i + 1] = X[i];
pos[0] = -INF;
pos[n - 1] = INF;
F0R (i, n) cows.insert({pos[i], i});
build(n - 1);
}
int update(int u, int y) {
u++;
erase(u);
insert(u, y);
push(tour);
return agg(tour) - 1;
}
