#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
int n, l;
int sqrtn;
vector<vector<pair<int, int>>> blocks;
vector<vector<pair<int, int>>> dp;
vector<pair<int, int>> id;
vector<int> a;
void init(int N, int L, int X[]) {
n = N;
l = L;
sqrtn = (int)sqrt(n);
blocks.resize(sqrtn);
id.resize(N);
int temp = 0;
for (int i = 0; i < n; i += sqrtn, temp++) {
for (int j = i; j < min(n, i+sqrtn); j++) {
blocks[temp].push_back({X[j], j});
id[j] = {temp, j-i};
a.push_back(X[j]);
}
}
dp.resize(sqrtn);
for (int i = 0; i < sqrtn; i++) {
dp[i].resize(blocks[i].size());
for (int j = blocks[i].size()-1; j >= 0; j--) {
dp[i][j] = {1, blocks[i][j].first+L};
auto it = upper_bound(blocks[i].begin(), blocks[i].end(), make_pair(blocks[i][j].first+L, n));
if (it != blocks[i].end()) {
int idx = it-blocks[i].begin();
dp[i][j].first += dp[i][idx].first;
dp[i][j].second = dp[i][idx].second;
}
}
}
}
int update(int i, int y) {
int cur = id[i].first, idx = id[i].second;
int nxt = sqrtn-1;
for (int j = 0; j < sqrtn; j++) {
if (blocks[j][0].first >= y) {
nxt = max(0, j-1);
break;
}
}
blocks[cur].erase(blocks[cur].begin()+idx);
for (int j = idx; j < blocks[cur].size(); j++)
id[blocks[cur][j].second].second = j;
blocks[nxt].push_back({y, i});
sort(blocks[nxt].begin(), blocks[nxt].end());
id[i].first = nxt;
for (int j = blocks[nxt].size()-1; j >= 0; j--) {
if (blocks[nxt][j].first == y) {
id[i].second = j;
break;
}
}
for (int j = id[i].second+1; j < blocks[nxt].size(); j++)
id[blocks[nxt][j].second].second++;
dp[cur].resize(blocks[cur].size());
for (int j = blocks[cur].size()-1; j >= 0; j--) {
dp[cur][j] = {1, blocks[cur][j].first+l};
auto it = upper_bound(blocks[cur].begin(), blocks[cur].end(), make_pair(blocks[cur][j].first+l, n));
if (it != blocks[cur].end()) {
int idx = it-blocks[cur].begin();
dp[cur][j].first += dp[cur][idx].first;
dp[cur][j].second = dp[cur][idx].second;
}
}
dp[nxt].resize(blocks[nxt].size());
for (int j = blocks[nxt].size()-1; j >= 0; j--) {
dp[nxt][j] = {1, blocks[nxt][j].first+l};
auto it = upper_bound(blocks[nxt].begin(), blocks[nxt].end(), make_pair(blocks[nxt][j].first+l, n));
if (it != blocks[nxt].end()) {
int idx = it-blocks[nxt].begin();
dp[nxt][j].first += dp[nxt][idx].first;
dp[nxt][j].second = dp[nxt][idx].second;
}
}
int ans = 0, k = 0;
for (int j = 0; j < sqrtn;) {
ans += dp[j][k].first;
int last = dp[j][k].second;
j++;
while (j < sqrtn) {
auto it = upper_bound(blocks[j].begin(), blocks[j].end(), make_pair(last, n));
if (it == blocks[j].end()) j++;
else {
k = it-blocks[j].begin();
break;
}
}
}
return ans;
}
