#include "elephants.h"
#include <vector>
#include <cmath>
#include <algorithm>
#define MAXN 150000
#define MAXR 150
#define MAXK 1000
#define LOGK 9
bool seen;
int n, l, k, r;
std::vector < int > v[MAXR];
int u[MAXN], p[MAXN], poz[MAXN];
struct myc {
int x, y;
} dp[MAXN];
inline void calc(std::vector < int > t) {
int j = t.size() - 1;
for (int i = t.size() - 1; i >= 0; i--) {
if (u[t[i]] + l >= u[t.back()]) dp[t[i]] = {1, u[t[i]] + l};
else {
while (j - 1 > i && u[t[j - 1]] > u[t[i]] + l)
j--;
dp[t[i]] = {1 + dp[t[j]].x, dp[t[j]].y};
}
}
}
void init(int N, int L, int X[]) {
if (seen == 0) {
n = N;
l = L;
k = MAXK;
seen = 1;
for (int i = 0; i < n; i++)
p[i] = i;
for (int i = 0; i < n; i++)
u[i] = X[i];
}
r = 1 + (n - 1) / k;
for (int i = 0; i < r; i++) {
v[i].resize(std::min(n, (i + 1) * k) - i * k);
for (int j = i * k; j < n && j < (i + 1) * k; j++)
v[i][j - i * k] = p[j], poz[p[j]] = i;
}
for (int i = r - 1; i >= 0; i--)
calc(v[i]);
}
inline void myInit() {
int aici[1] = {0};
int j = 0;
for (int i = 0; i < r; i++)
for (auto &x : v[i])
p[j++] = x;
init(0, 0, aici);
}
inline void scoate(int p) {
int i = 0;
while (v[poz[p]][i] != p)
i++;
while (i + 1 < (int)v[poz[p]].size()) {
v[poz[p]][i] = v[poz[p]][i + 1];
i++;
}
v[poz[p]].pop_back();
}
inline void baga(int p) {
int i = 0;
while (i < (int)v[poz[p]].size() && u[v[poz[p]][i]] < u[p])
i++;
v[poz[p]].push_back(0);
for (int j = v[poz[p]].size() - 1; j > i; j--)
v[poz[p]][j] = v[poz[p]][j - 1];
v[poz[p]][i] = p;
}
int update(int i, int y) {
int e = 0, f = poz[i];
for (int pas = 1 << 8; pas; pas >>= 1)
if (e + pas < r && u[v[e + pas][0]] <= y)
e += pas;
scoate(i);
poz[i] = e;
u[i] = y;
baga(i);
if (f == e)
calc(v[e]);
else if (((int)v[f].size() == 0 && f != r - 1) || (int)v[e].size() == 2 * r)
myInit();
else if (e < f) {
if ((int)v[f].size() == 0)
r--;
else
calc(v[f]);
calc(v[e]);
} else {
calc(v[e]);
calc(v[f]);
}
int val = -1, ans = 0;
for (int i = 0; i < r; i++) {
if (val < u[v[i].back()]) {
int rez = -1;
for (int pas = 1 << LOGK; pas; pas >>= 1)
if (rez + pas < (int)v[i].size() && u[v[i][rez + pas]] <= val)
rez += pas;
rez++;
ans += dp[v[i][rez]].x;
val = dp[v[i][rez]].y;
}
}
return ans;
}
