#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1.5e5 + 20;
const int block_size = 1000;
vector<int> pos[maxN];
vector<pair<int, int>> dp[maxN];
int A[maxN];
int N, L;
int block_cnt;
void calc_block(int id) {
vector<int> &pos_block = pos[id];
vector<pair<int, int>> &dp_block = dp[id];
int sz = pos_block.size();
dp_block.resize(sz);
int rt = sz;
for (int i = sz - 1; i >= 0; i--) {
while (pos_block[rt - 1] > pos_block[i] + L) {
rt--;
}
if (rt == sz) {
dp_block[i].first = 1;
dp_block[i].second = pos_block[i];
}
else {
dp_block[i].first = dp_block[rt].first + 1;
dp_block[i].second = dp_block[rt].second;
}
}
}
int calc_all() {
int res = dp[0][0].first;
int last = dp[0][0].second;
for (int id = 1; id < block_cnt; id++) {
if (pos[id].back() > last + L) {
int i = upper_bound(pos[id].begin(), pos[id].end(), last + L) - pos[id].begin();
res += dp[id][i].first;
last = dp[id][i].second;
}
}
return res;
}
void rem(int X) {
int id = 0;
while (pos[id].back() < X) {
id++;
}
pos[id].erase(lower_bound(pos[id].begin(), pos[id].end(), X));
if (pos[id].empty()) {
for (int i = id + 1; i < block_cnt; i++) {
swap(pos[i - 1], pos[i]);
swap(dp[i - 1], dp[i]);
}
block_cnt--;
}
else {
calc_block(id);
}
}
void add(int X) {
int id = 0;
while (id < block_cnt && pos[id].back() < X) {
id++;
}
if (id == block_cnt) {
block_cnt++;
}
pos[id].insert(upper_bound(pos[id].begin(), pos[id].end(), X), X);
if ((int)pos[id].size() == block_size * 2) {
for (int i = block_cnt - 1; i > id; i--) {
swap(pos[i + 1], pos[i]);
swap(dp[i + 1], dp[i]);
}
pos[id + 1].insert(pos[id + 1].begin(), pos[id].begin() + block_size, pos[id].end());
pos[id].erase(pos[id].begin() + block_size, pos[id].end());
block_cnt++;
calc_block(id);
calc_block(id + 1);
}
else {
calc_block(id);
}
}
void init(int _N, int _L, int _A[]) {
N = _N;
L = _L;
block_cnt = (N - 1) / block_size + 1;
for (int i = 0; i < N; i++) {
A[i] = _A[i];
pos[i / block_size].push_back(A[i]);
}
for (int id = 0; id < block_cnt; id++) {
calc_block(id);
}
}
int update(int i, int X) {
rem(A[i]);
A[i] = X;
add(A[i]);
return calc_all();
}
