#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
const int K = 500;
int upd = 0;
int N, L;
vector<int> pos;
vector<vector<int>> block, X, Y;
void calc(int j) {
X[j].assign(block[j].size(), 0), Y[j].assign(block[j].size(), 0);
for(int i = block[j].size()-1; i >= 0; i--) {
int e = block[j][i];
int l = i + 1, r = block[j].size();
while(l < r) {
int m = (l + r) / 2;
if (pos[e] + L >= pos[block[j][m]]) l = m + 1;
else r = m;
}
X[j][i] = 1 + (l == block[j].size() ? 0 : X[j][l]);
Y[j][i] = (l == block[j].size() ? pos[e] + L : Y[j][l]);
}
}
void build() {
block.assign(N/K + (N%K>0), vector<int>()), X.assign(N/K + (N%K>0), vector<int>()), Y.assign(N/K + (N%K>0), vector<int>());
vector<int> order(N); iota(all(order), 0);
sort(all(order), [&](const int a, const int b) {return pos[a] < pos[b];});
for(int j = 0; j < block.size(); j++) {
for(int i = j * K; i < N && i < (j+1) * K; i++) block[j].push_back(order[i]);
calc(j);
}
}
int solve() {
int res = 0, cur = -1;
for(int j = 0; j < block.size(); j++) {
int l = 0, r = block[j].size();
while(l < r) {
int m = (l + r) / 2;
if (pos[block[j][m]] <= cur) l = m + 1;
else r = m;
}
if (l != block[j].size()) res += X[j][l], cur = Y[j][l];
}
return res;
}
void init(int N, int L, int pos[]) {
::N = N, ::L = L;
::pos.resize(N);
for(int i = 0; i < N; i++) ::pos[i] = pos[i];
build();
}
int update(int e, int p) {
for(int j = 0; j < block.size(); j++) {
if (block[j].empty()) continue;
if (pos[block[j].front()] <= pos[e] && pos[e] <= pos[block[j].back()]) {
auto it = find(all(block[j]), e); /////////
if (it != block[j].end()) {
block[j].erase(it);
calc(j);
break;
}
}
}
pos[e] = p;
for(int j = 0; j < block.size(); j++) {
if (block[j].empty()) continue;
if (pos[block[j].front()] <= pos[e] && pos[e] <= pos[block[j].back()]) {
for(int i = 0; i < block[j].size(); i++) {
if (pos[block[j][i]] >= pos[e]) {
block[j].insert(block[j].begin() + i, e);
break;
}
}
calc(j);
break;
} else if (pos[block[j].front()] > pos[e]) {
block[j].insert(block[j].begin(), e);
calc(j);
break;
} else if (pos[block[j].back()] < pos[e] &&
(j == block.size()-1 || (block[j+1].size() && pos[e] < pos[block[j+1].front()]))) {
block[j].push_back(e);
calc(j);
break;
}
}
upd++;
if (upd % K == 0) build();
return solve();
}
