#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
class node {
public:
node* l;
node* r;
node* p;
bool is;
int sz;
node(bool is): is(is) {
l = r = p = NULL;
sz = is;
}
void pull() {
sz = is;
if (l != NULL) {
l->p = this;
sz += l->sz;
}
if (r != NULL) {
r->p = this;
sz += r->sz;
}
}
};
bool is_bst_root(node* v) {
if (v == NULL) {
return false;
}
return (v->p == NULL || (v->p->l != v && v->p->r != v));
}
void rotate(node* v) {
node* u = v->p;
v->p = u->p;
if (v->p != NULL) {
if (v->p->l == u) {
v->p->l = v;
}
if (v->p->r == u) {
v->p->r = v;
}
}
if (v == u->l) {
u->l = v->r;
v->r = u;
} else {
u->r = v->l;
v->l = u;
}
u->pull();
v->pull();
}
void splay(node* v) {
if (v == NULL) {
return;
}
while (!is_bst_root(v)) {
node* u = v->p;
if (!is_bst_root(u)) {
if ((u->l == v) ^ (u->p->l == u)) {
rotate(v);
} else {
rotate(u);
}
}
rotate(v);
}
}
void access(node* v) {
node* u = NULL;
while (v != NULL) {
splay(v);
v->r = u;
v->pull();
u = v;
v = v->p;
}
}
void link(node* v, node* u) {
splay(v);
v->p = u;
}
void cut(node* v, node* u) {
access(v);
splay(u);
u->r = v->p = NULL;
u->pull();
}
set<pair<int, int>> all, white;
vector<node*> tree;
vector<int> x, to;
int n, m;
int find_next(pair<int, int> p) {
return all.upper_bound(p)->second;
}
void init(int N, int L, int X[]) {
n = N;
m = L;
for (int i = 0; i < n; ++i) {
x.push_back(X[i]);
}
for (int i = 0; i < n * 2 + 2; ++i) {
tree.push_back(new node(i < n));
to.push_back(-1);
}
all.emplace(-1, n * 2);
white.emplace(-1, n * 2);
for (int i = 0; i < n; ++i) {
all.emplace(x[i], i);
all.emplace(x[i] + m, i + n);
white.emplace(x[i] + m, i + n);
to[i] = i + n;
link(tree[i], tree[i + n]);
}
all.emplace(INT_MAX, n * 2 + 1);
for (auto p : white) {
to[p.second] = find_next(p);
link(tree[p.second], tree[to[p.second]]);
}
}
int update(int i, int y) {
all.erase(make_pair(x[i], i));
all.erase(make_pair(x[i] + m, i + n));
white.erase(make_pair(x[i] + m, i + n));
cut(tree[i + n], tree[to[i + n]]);
to[i + n] = -1;
{
auto it = --white.lower_bound(make_pair(x[i], i));
cut(tree[it->second], tree[to[it->second]]);
to[it->second] = find_next(*it);
link(tree[it->second], tree[to[it->second]]);
}
{
auto it = --white.lower_bound(make_pair(x[i] + m, i + n));
cut(tree[it->second], tree[to[it->second]]);
to[it->second] = find_next(*it);
link(tree[it->second], tree[to[it->second]]);
}
x[i] = y;
all.insert(make_pair(x[i], i));
all.insert(make_pair(x[i] + m, i + n));
white.insert(make_pair(x[i] + m, i + n));
to[i + n] = find_next(make_pair(x[i] + m, i + n));
link(tree[i + n], tree[to[i + n]]);
{
auto it = --white.lower_bound(make_pair(x[i], i));
cut(tree[it->second], tree[to[it->second]]);
to[it->second] = find_next(*it);
link(tree[it->second], tree[to[it->second]]);
}
{
auto it = --white.lower_bound(make_pair(x[i] + m, i + n));
cut(tree[it->second], tree[to[it->second]]);
to[it->second] = find_next(*it);
link(tree[it->second], tree[to[it->second]]);
}
access(tree[n * 2]);
splay(tree[n * 2]);
return tree[n * 2]->sz;
}
