#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
int n, l;
int sqrtn;
vector<vector<int>> blocks;
vector<vector<int>> ids;
vector<vector<pair<int, int>>> dp;
vector<pair<int, int>> loc; // block no., position in the block
int q_cnt = 0;
void calc(int i) {
for (int j = blocks[i].size()-1; j >= 0; j--) {
dp[i][j] = {1, blocks[i][j]+l};
auto it = upper_bound(blocks[i].begin(), blocks[i].end(), blocks[i][j]+l);
if (it != blocks[i].end()) {
int idx = it-blocks[i].begin();
dp[i][j].first += dp[i][idx].first;
dp[i][j].second = dp[i][idx].second;
}
}
}
void init(int N, int L, int X[]) {
n = N;
l = L;
loc.resize(n);
sqrtn = (int)sqrt(n);
blocks.resize(sqrtn);
ids.resize(sqrtn);
for (int i = 0, idx = 0; i < n; i += sqrtn, idx++) {
for (int j = i; j < min(n, i+sqrtn); j++) {
blocks[idx].push_back(X[j]);
ids[idx].push_back(j);
loc[j] = {idx, j-i};
}
}
dp.resize(sqrtn);
for (int i = 0; i < sqrtn; i++) {
dp[i].resize(blocks[i].size());
calc(i);
}
}
void remove(int i) {
int b = loc[i].first, x = loc[i].second;
// remove this elephant from its current block
blocks[b].erase(blocks[b].begin()+x);
ids[b].erase(ids[b].begin()+x);
// renumber all the elephants from this block
for (int j = 0; j < blocks[b].size(); j++) loc[ids[b][j]] = {b, j};
}
void add(int val, int i, int nxt) {
vector<int> new_block, new_ids;
bool done = false;
for (int j = 0; j < blocks[nxt].size(); j++) {
if (!done && blocks[nxt][j] > val) {
new_block.push_back(val);
new_ids.push_back(i);
loc[i] = {nxt, j};
done = true;
}
new_block.push_back(blocks[nxt][j]);
new_ids.push_back(ids[nxt][j]);
loc[ids[nxt][j]] = {nxt, j};
if (done) loc[ids[nxt][j]].second++;
}
if (!done) {
new_block.push_back(val);
new_ids.push_back(i);
loc[i] = {nxt, new_block.size()-1};
}
swap(blocks[nxt], new_block);
swap(ids[nxt], new_ids);
}
void adjust() {
q_cnt = 0;
vector<vector<int>> blocks_new(sqrtn);
vector<vector<int>> ids_new(sqrtn);
int idx = 0;
for (int i = 0; i < sqrtn; i++) {
for (int j = 0; j < blocks[i].size(); j++) {
blocks_new[idx].push_back(blocks[i][j]);
ids_new[idx].push_back(ids[i][j]);
if (blocks_new[idx].size() == sqrtn) idx++;
}
}
for (int i = 0; i < sqrtn; i++) {
for (int j = 0; j < blocks_new[i].size(); j++)
loc[ids_new[i][j]] = {i, j};
}
swap(blocks, blocks_new);
swap(ids, ids_new);
}
int update(int i, int y) {
int cur = loc[i].first;
remove(i);
bool added = false;
int nxt = sqrtn-1;
for (int j = 0; j < sqrtn; j++) {
if (y <= blocks[j].back()) {
add(y, i, j);
added = true;
nxt = j;
break;
}
}
if (!added) add(y, i, sqrtn-1);
dp[cur].resize(blocks[cur].size());
calc(cur);
dp[nxt].resize(blocks[nxt].size());
calc(nxt);
int ans = 0;
for (int j = 0, k = 0; j < sqrtn;) {
if (dp[j].empty()) {
j++;
continue;
}
ans += dp[j][k].first;
int last = dp[j][k].second;
j++;
while (j < sqrtn) {
auto it = upper_bound(blocks[j].begin(), blocks[j].end(), last);
if (it == blocks[j].end()) j++;
else {
k = it-blocks[j].begin();
break;
}
}
}
q_cnt++;
if (q_cnt >= sqrtn) adjust();
return ans;
}
