#include "elephants.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1.5e5 + 5;
const int B = 390;
int n, k;
int start[B], pos[N], id[N], jump[N], cnt[N];
vector<pii> bucket[B + 1];
set<pii> S;
void solve_bucket(int idx) {
vector<pii> &vec = bucket[idx];
for(int i = vec.size() - 1; ~i; i--) {
int now, x; tie(x, now) = vec[i];
auto it = S.lower_bound(pii(x + k + 1, -1e9));
if(it == S.end()) jump[now] = -1, cnt[now] = 1;
else {
if(id[it->y] != idx) jump[now] = it->y, cnt[now] = 1;
else jump[now] = jump[it->y], cnt[now] = cnt[it->y] + 1;
}
}
}
void init(int _n, int _k, int X[]) {
n = _n, k = _k;
fill_n(start, B, 1e9);
for(int i = 0; i < n; i++) {
pos[i] = X[i], id[i] = i / B;
bucket[i / B].emplace_back(pos[i], i);
S.emplace(pos[i], i);
}
for(int i = 0; i < B; i++) if(!bucket[i].empty()) {
start[i] = bucket[i][0].x;
solve_bucket(i);
}
}
void add(int i, bool b) {
int ptr = 0;
while(ptr + 1 < B && start[ptr + 1] <= pos[i])
++ptr;
int idx = lower_bound(bucket[ptr].begin(), bucket[ptr].end(), pii(pos[i], i)) - bucket[ptr].begin();
if(b) {
bucket[ptr].insert(bucket[ptr].begin() + idx, pii(pos[i], i));
S.emplace(pos[i], i);
} else {
bucket[ptr].erase(bucket[ptr].begin() + idx);
S.erase(pii(pos[i], i));
}
solve_bucket(ptr);
}
void revalidate() {
fill_n(start, B, 1e9);
int ptr = 0;
for(pii p : S) {
if(!ptr || (ptr - 1) / B != ptr / B)
bucket[ptr / B].clear();
bucket[ptr / B].emplace_back(p);
++ptr;
}
for(int i = 0; i < B; i++) if(!bucket[i].empty()) {
start[i] = bucket[i][0].x;
solve_bucket(i);
}
}
int counter;
int update(int i, int y) {
if(++counter % B == 0)
revalidate();
add(i, 0);
pos[i] = y;
add(i, 1);
// for(int i = 0; i < n; i++) printf("(%d %d)\n", jump[i], cnt[i]);
int now = S.begin()->y, answer = 0;
while(now != -1) {
answer += cnt[now];
now = jump[now];
}
// printf("answer = %d\n", answer);
return answer;
}
