#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int N = 150000 + 7;
const int B = 400;
int n, len, normal_ord[N], rad, mx, v[N];
vector<int> bucket[B];
int ind;
void init(int nn, int lenlen, int initial[]) {
n = nn;
len = lenlen;
ind = 0;
rad = sqrt(nn);
mx = (n - 1) / rad;
for (int i = 0; i < B; i++) {
bucket[i].clear();
}
for (int i = 0; i < n; i++) {
normal_ord[i] = initial[i];
}
}
void print(int v[]) {
cout << " ----> ";
for (int i = 0; i < n; i++) {
cout << v[i] << " ";
}
cout << "\n";
}
int update(int ii, int yy) {
if (ind % rad == 0) {
/// It's rebuild time
vector<int> values;
for (int i = 0; i < n; i++) {
values.push_back(normal_ord[i]);
}
sort(values.begin(), values.end());
for (int i = 0; i <= mx; i++) {
bucket[i].clear();
}
for (int i = 0; i < n; i++) {
bucket[i / rad].push_back(values[i]);
}
}
ind++;
{
int value = normal_ord[ii];
normal_ord[ii] = yy;
bool found = 0;
for (int i = 0; i <= mx; i++) {
if (bucket[i].empty()) continue;
if (bucket[i][0] <= value && value <= bucket[i].back()) {
int pos = -1;
for (int j = 0; j < (int) bucket[i].size(); j++) {
if (bucket[i][j] == value) {
pos = j;
break;
}
}
vector<int> new_bucket;
for (int j = 0; j < (int) bucket[i].size(); j++) {
if (j != pos) {
new_bucket.push_back(bucket[i][j]);
}
}
bucket[i] = new_bucket;
assert(pos != -1);
found = 1;
break;
}
}
assert(found);
int where = mx;
for (int i = 0; i <= mx; i++) {
if (bucket[i].empty()) continue;
if (bucket[i].back() >= yy) {
where = i;
break;
}
}
bucket[where].push_back(yy);
int j = (int) bucket[where].size() - 1;
while (j - 1 >= 0 && bucket[where][j - 1] > bucket[where][j]) {
swap(bucket[where][j - 1], bucket[where][j]);
j--;
}
}
{
int sz = 0;
for (int i = 0; i <= mx; i++) {
for (int j = 1; j < (int) bucket[i].size(); j++) {
assert(bucket[i][j - 1] <= bucket[i][j]);
}
for (auto &x : bucket[i]) {
v[sz++] = x;
}
}
}
int cost = 0, l = 0;
while (l < n) {
cost++;
int r = l;
while (r + 1 < n && v[r + 1] - v[l] <= len) {
r++;
}
l = r + 1;
}
return cost;
}
