#include "elephants.h"
#include "bits/stdc++.h"
using namespace std;
vector<int> J, T, P, A;
vector<vector<int>> B;
int n, l, k, m;
void calc_bucket(int i) {
int j = (int)B[i].size() - 1, j_dum = 0, t_dum = -1;
for (int k = j; k >= 0; k --) {
for (; P[B[i][j]] - P[B[i][k]] > l; j --) {
j_dum = J[B[i][j]], t_dum = T[B[i][j]];
}
J[B[i][k]] = j_dum + 1, T[B[i][k]] = max(t_dum, P[B[i][k]] + l);
}
}
void build_buckets() {
vector<int> o(n);
iota(begin(o), end(o), 0);
sort(begin(o), end(o), [](int i, int j) {
return P[i] < P[j];
});
A.resize(n);
B.clear();
B.push_back({n});
for (int i = 0; i < n; i ++) {
if (B.empty() or (int)B.back().size() > k) {
B.push_back({});
J.push_back({});
T.push_back({});
}
B.back().push_back(o[i]);
A[i] = (int)B.size() - 1;
}
J.assign(n, 0);
T.assign(n, 0);
for (int i = 0; i < B.size(); i ++) {
calc_bucket(i);
}
}
void init(int N, int L, int X[]) {
n = N, l = L, k = sqrt(N);
P.resize(N + 1);
P[n] = -1;
for (int i = 0; i < N; i ++) {
P[i] = X[i];
}
build_buckets();
}
int update(int i, int y) {
for (int j = 0; j < (int)B[A[i]].size(); j ++) {
if (B[A[i]][j] == i) {
B[A[i]].erase(begin(B[A[i]]) + j);
calc_bucket(A[i]);
break;
}
}
P[i] = y;
for (int j = (int)B.size() - 1; j >= 0; j --) {
if (not B[j].empty() and P[B[j].front()] <= P[i]) {
int k = 0;
for (; k < (int)B[j].size(); k ++) {
if (P[B[j][k]] > P[i]) {
break;
}
}
B[j].insert(begin(B[j]) + k, i);
calc_bucket(j);
A[i] = j;
break;
}
}
int last_pos = -1, answer = 0;
for (int i = 0; i < (int)B.size(); i ++) {
int bs = -1;
for (int l = 0, r = (int)B[i].size() - 1; l <= r;) {
int mi = (l + r) / 2;
if (P[B[i][mi]] > last_pos) {
bs = mi, r = mi - 1;
} else {
l = mi + 1;
}
}
if (bs != -1) {
answer += J[B[i][bs]], last_pos = T[B[i][bs]];
}
}
m ++;
if (m == k) {
build_buckets();
}
return answer;
}
