#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "elephants.h"
#define ar array
using namespace std;
const int mxN = 15e4;
int n, l, R, a[mxN], idxs[mxN], where[mxN];
struct Chunk {
int size;
vector<int> xs;
vector<ar<int, 2>> dp;
Chunk(vector<int> &&_xs) : size((int)_xs.size()), xs(move(_xs)) {
dp.resize(size);
recalc(size-1);
}
void recalc(int from) {
for (int i = from; i >= 0; --i) {
int j = lower_bound(xs.begin(), xs.end(), xs[i]+l) - xs.begin();
if (j == size) dp[i] = {1, xs[i]+l};
else dp[i] = {dp[j][0]+1, dp[j][1]};
}
}
void insert(int x) {
++size;
int i = int(upper_bound(xs.begin(), xs.end(), x) - xs.begin());
xs.insert(xs.begin()+i, x);
dp.insert(dp.begin()+i, {0, 0});
recalc(i);
}
void erase(int x) {
--size;
int i = int(lower_bound(xs.begin(), xs.end(), x) - xs.begin());
dp.erase(dp.begin() + i);
xs.erase(xs.begin() + i);
recalc(i-1);
}
ar<int, 2> qry(int x) {
int j = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
if (j == size) return {0, x};
return dp[j];
}
};
vector<Chunk> chunks;
void recalc() {
iota(idxs, idxs+n, 0);
sort(idxs, idxs+n, [&](int i, int j){ return a[i] < a[j]; });
chunks.clear();
for (int i0 = 0; i0 < n; i0 += R) {
vector<int> xs;
for (int i = i0; i < min(i0+R, n); ++i) {
xs.push_back(a[idxs[i]]);
where[idxs[i]] = (int)chunks.size();
}
chunks.emplace_back(move(xs));
}
}
void init(int N, int L, int X[]) {
n = N, l = L+1;
for (int i = 0; i < n; ++i)
a[i] = X[i];
R = sqrt(N);
recalc();
}
int solve() {
int x = -1e9-10, ans = 0;
for (int c = 0; c < (int)chunks.size(); ++c) {
auto [used, new_x] = chunks[c].qry(x);
ans += used;
x = new_x;
}
return ans;
}
int update(int i, int y) {
static int update_cnt = 0;
if (++update_cnt%R == 0) {
a[i] = y;
recalc();
} else {
int c = where[i];
chunks[c].erase(a[i]);
a[i] = y;
for (c = 1; c < (int)chunks.size(); ++c)
if (chunks[c].size && chunks[c].xs[0] > a[i]) break;
--c;
chunks[c].insert(a[i]);
where[i] = c;
}
return solve();
}
