#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
constexpr size_t MAX_N = 151000, B = 387;
int l;
struct Bucket
{
size_t n;
int x[2 * B], k[2 * B], o[2 * B];
void build(size_t m) // Recalculate the first m elephants.
{
size_t i = m - 1, j = upper_bound(x, x + n, x[i] + l) - x;
while (i < m)
{
while (j > i + 1 && x[i] + l < x[j - 1])
--j;
if (j == n)
k[i] = 1, o[i] = x[i] + l;
else
k[i] = k[j] + 1, o[i] = o[j];
--i;
}
}
void insert(int y)
{
x[n] = y;
size_t i = n;
while (i && x[i] < x[i - 1])
swap(x[i], x[i - 1]), swap(k[i], k[i - 1]), swap(o[i], o[i - 1]), --i;
++n;
build(i + 1);
}
void erase(size_t i)
{
for (size_t j = i; j < n - 1; ++j)
swap(x[j], x[j + 1]), swap(k[j], k[j + 1]), swap(o[j], o[j + 1]);
--n;
if (i)
build(i);
}
};
size_t iteration_count = 0;
Bucket b[MAX_N / B];
int u[MAX_N], v[MAX_N];
void init(int N, int L, int X[])
{
l = L;
for (size_t i = 0; i <= N / B; ++i)
{
for (size_t j = 0; j < B && i * B + j < N; ++j)
b[i].x[j] = X[i * B + j], ++b[i].n;
b[i].build(b[i].n);
}
memcpy(u, X, N * sizeof *X);
}
int update(int i, int y)
{
if (iteration_count == B - 1)
{
size_t k = 0;
for (size_t i = 0; i < MAX_N / B; ++i)
{
for (size_t j = 0; j < b[i].n; ++j)
v[k++] = b[i].x[j];
b[i].n = 0;
}
for (size_t i = 0; i <= k / B; ++i)
{
for (size_t j = 0; j < B && i * B + j < k; ++j)
b[i].x[j] = v[i * B + j], ++b[i].n;
b[i].build(b[i].n);
}
iteration_count = 0;
}
++iteration_count;
for (size_t j = 0;; ++j)
if (b[j].x[0] <= u[i] && u[i] <= b[j].x[b[j].n - 1])
{
b[j].erase(lower_bound(b[j].x, b[j].x + b[j].n, u[i]) - b[j].x);
break;
}
u[i] = y;
for (size_t j = 0;; ++j)
if ((!j || b[j].x[0] <= y) && (!b[j + 1].n || y <= b[j + 1].x[0]))
{
b[j].insert(y);
break;
}
int covered = -1, cameras = 0;
for (size_t j = 0; b[j].n; ++j)
if (b[j].x[b[j].n - 1] > covered)
{
size_t const k = upper_bound(b[j].x, b[j].x + b[j].n, covered) - b[j].x;
covered = b[j].o[k];
cameras += b[j].k[k];
}
return cameras;
}
