#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include "elephants.h"
using namespace std;
const int INF = 1e9 + 1;
const int N = 15e4;
const int SQRT = 600;
int pos[N];
vector <int> bucket[SQRT];
int toDate[SQRT];
vector <pair <int, int>> jump[SQRT];
int nbElephants, length;
void build_bucket(int id) {
int sz = size(bucket[id]);
jump[id].resize(sz);
int nxt = 0, nxtId = id;
while (!bucket[nxtId].empty() && bucket[nxtId][0] <= bucket[id].back() + length)
nxtId ++;
nxtId --;
while (nxt < (int)size(bucket[nxtId]) && bucket[nxtId][nxt] <= bucket[id].back() + length)
nxt ++;
nxt --;
for (int i = sz - 1; i >= 0; i --)
{
while (bucket[nxtId][nxt] > bucket[id][i] + length)
if (!(nxt --))
nxt = size(bucket[-- nxtId]) - 1;
if (nxtId > id || nxt == sz - 1)
jump[id][i] = {1, nxtId * 2 * SQRT + nxt};
else
jump[id][i] = {1 + jump[id][nxt + 1].first, jump[id][nxt + 1].second};
}
toDate[id] = 1;
return;
}
void update_bucket(int id) {
int cur = id - 1;
while (cur >= 0)// && bucket[cur].back() + length >= bucket[id][0])
toDate[cur --] = 0;
return;
}
void insert(int id, int val) {
vector <int> nv;
for (int a : bucket[id])
{
if (a >= val)
{
nv.push_back(val);
val = INF;
}
nv.push_back(a);
}
if (val < INF)
nv.push_back(val);
bucket[id] = nv;
build_bucket(id);
update_bucket(id);
return;
}
void remove(int id, int val) {
vector <int> nv;
for (int a : bucket[id])
{
if (a == val)
val = -1;
else
nv.push_back(a);
}
bucket[id] = nv;
update_bucket(id);
build_bucket(id);
return;
}
int answer() {
int ans = 0, cur = 0, id = 0;
while (!bucket[id].empty())
{
if (!toDate[id])
build_bucket(id);
ans += jump[id][cur].first;
int jmp = jump[id][cur].second;
id = jmp / (2 * SQRT), cur = jmp % (2 * SQRT);
if (++ cur == (int)size(bucket[id]))
id ++, cur = 0;
}
return ans;
}
void reset_buckets() {
vector <int> allPos;
int cur = 0;
while (!bucket[cur].empty())
{
for (int a : bucket[cur])
allPos.push_back(a);
bucket[cur ++].clear();
}
cur = 0;
for (int i = 0; i < nbElephants; i ++)
{
if ((int)size(bucket[cur]) > SQRT && (nbElephants - i) >= SQRT / 2)
cur ++;
bucket[cur].push_back(allPos[i]);
}
for (int i = 0; i <= cur; i ++)
build_bucket(i);
return;
}
void init(int N, int L, int X[]) {
nbElephants = N;
length = L;
for (int i = 0; i < nbElephants; i ++)
bucket[0].push_back(pos[i] = X[i]);
sort(bucket[0].begin(), bucket[0].end());
reset_buckets();
return;
}
int find(int val) {
int cur = 0;
while (!bucket[cur].empty() && bucket[cur].back() < val)
cur ++;
return cur - bucket[cur].empty();
}
int update(int id, int nv) {
int prev = pos[id];
pos[id] = nv;
bool reset = false;
int cur = find(prev);
remove(cur, prev);
reset |= size(bucket[cur]) <= 1;
cur = find(nv);
insert(cur, nv);
reset |= size(bucket[cur]) >= 2 * SQRT;
if (reset)
reset_buckets();
return answer();
}
