#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 151000, C = 512;
struct node {
node *l, *r, *p, *pp;
int val, sum;
node(int x = 0) : l(0), r(0), p(0), pp(0), val(x), sum(x) {}
};
using pnode = node*;
void upd(pnode v) {
if(!v) return;
v->sum = v->val;
for(auto i : {v->l, v->r}) if(i) {
i->p = v;
v->sum += i->sum;
}
}
void rotate(pnode v) {
auto p = v->p, g = p->p;
if(g) (g->l == p ? g->l : g->r) = v;
else v->p = 0;
if(p->l == v)
p->l = v->r, v->r = p;
else
p->r = v->l, v->l = p;
upd(p), upd(v), upd(g);
}
pnode splay(pnode v) {
if(!v) return 0;
while(v->p) {
auto p = v->p, g = p->p;
if(g)
rotate((g->l == p) == (p->l == v) ? p : v);
rotate(v);
}
return v;
}
pnode left(pnode v) {
splay(v);
while(v->l) v = v->l;
return splay(v);
}
void cut_r(pnode v) {
splay(v);
if(!v->r) return;
auto t = v->r;
t->p = v->r = 0;
upd(v);
t = left(t);
t->pp = v;
}
pnode merge(pnode a, pnode b) {
if(!a||!b) return a?:b;
b = left(b);
b->l = a;
b->pp = 0;
upd(b);
return a;
}
void expose(pnode v) {
cut_r(v);
v = left(v);
while(v->pp) {
cut_r(v->pp);
v = left(merge(v->pp, v));
}
}
pnode root(pnode a) {
expose(a);
return left(a);
}
void link(pnode a, pnode b) {
assert(root(a) != root(b));
expose(b);
a->pp = b;
}
void cut(pnode a, pnode b) {
expose(b);
a->pp = 0;
}
pnode lca(pnode a, pnode b) {
expose(a);
if(left(a)->val == left(b)->val) return b;
expose(b);
if(left(a)->val == left(b)->val) return a;
return left(a)->pp;
}
deque<node> buffer;
pnode newnode(int x = 0) {
buffer.emplace_back(x);
return &buffer.back();
}
int n, l;
pnode nd[maxn];
int pos[maxn], curp[maxn];
set<array<int, 2>> f;
int next(int v) {
auto it = f.upper_bound({pos[v], v});
return it==f.end()?-1:it->at(1);
}
int jump(int v) {
auto it = f.upper_bound({pos[v]+l, 1<<30});
return it==f.end()?-1:it->at(1);
}
void kill(int v) {
if(curp[v] != -1) {
if(curp[v] != -1)
cut(nd[v], nd[curp[v]]);
nd[v]->val = 0;
upd(nd[v]);
curp[v] = -1;
}
}
void make_link(int v) {
kill(v);
int x = next(v);
int y = jump(v);
if(x == -1)
return;
if(jump(x) == y) {
//cout << v << " points(0) to " << x << " | " << pos[v] << " " << pos[x] << endl;
link(nd[v], nd[x]);
curp[v] = x;
} else if(y != -1) {
//cout << v << " points(1) to " << y << " | " << pos[v] << " " << pos[y] << endl;
link(nd[v], nd[y]);
curp[v] = y;
nd[v]->val = 1;
upd(nd[v]);
}
}
void init(int N, int L, int X[]) {
n = N, l = L;
for(int i = 0; i < n; i++) {
f.insert({X[i], i});
pos[i] = X[i];
curp[i] = -1;
nd[i] = newnode(0);
}
for(int i = 0; i < n; i++) make_link(i);
}
void event(int x, int y) {
auto P = f.lower_bound({x, y});
if(P != f.begin()) {
P--;
make_link(P->at(1));
}
P = f.lower_bound({x-l, -1});
if(P != f.begin()) {
P--;
make_link(P->at(1));
}
}
int update(int i, int y) {
//cout << "Query\n";
auto V = f.lower_bound({pos[i], i});
kill(i);
f.erase({pos[i], i});
event(pos[i], i);
f.insert({pos[i] = y, i});
event(y, i);
make_link(i);
//for(int i = 0; i < n; i++) cout << pos[i] << " " << jump(i) << '\n';
return 1+root(nd[f.begin()->at(1)])->sum;
}
