#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 15e4 + 5;
const int SIZE = 700;
int n, len, max_block_id, cnt_query = 0, x[lim], tx[lim];
struct DataStructure{
int start;
vector<pair<int, int>>val;
vector<int>f, en;
void reset(){
val.clear();
f.clear();
en.clear();
}
void rebuild(){
f.resize(val.size());
en.resize(val.size());
for(int l = int(f.size()) - 1, r = l; l > -1; l--){
while(val[r].first > val[l].first + len){
r--;
}
if(r == int(f.size()) - 1){
f[l] = 1;
en[l] = val[l].first + len + 1;
}
else{
f[l] = f[r + 1] + 1;
en[l] = en[r + 1];
}
}
}
void remove(int x){
vector<pair<int, int>>::iterator it = lower_bound(val.begin(), val.end(), make_pair(x, -1));
if(--it->second == 0){
val.erase(it);
rebuild();
}
}
void add(int x){
vector<pair<int, int>>::iterator it = lower_bound(val.begin(), val.end(), make_pair(x, -1));
if(it != val.end() && it->first == x){
it->second++;
}
else{
val.insert(it, make_pair(x, 1));
rebuild();
}
}
pair<int, int>get(int start){
if(val.empty() || start > val.back().first){
return make_pair(0, start);
}
int p = lower_bound(val.begin(), val.end(), make_pair(start, -1)) - val.begin();
return make_pair(f[p], en[p]);
}
};
DataStructure ds[lim / SIZE + 2];
void init(int _N, int _L, int _X[]){
max_block_id = (n = _N) / SIZE + 1;
len = _L;
for(int i = 0; i < n; i++){
x[i] = _X[i];
}
}
int get_block_id(int y){
int low = 0, high = max_block_id, p;
while(low <= high){
int mid = (low + high) >> 1;
if(ds[mid].start > y){
high = mid - 1;
}
else{
low = (p = mid) + 1;
}
}
return p;
}
int update(int p, int y){
if(cnt_query++ % SIZE == 0){
memcpy(tx, x, sizeof(tx));
sort(tx, tx + n);
ds[ds[0].start = 0].reset();
for(int i = 1; i <= max_block_id; i++){
ds[i].start = max(ds[i - 1].start + 1, tx[(i - 1) * SIZE]);
ds[i].reset();
}
for(int i = 0, j = 0; i < n; i++){
while(j < max_block_id && ds[j + 1].start <= tx[i]){
j++;
}
ds[j].add(tx[i]);
}
}
ds[get_block_id(x[p])].remove(x[p]);
ds[get_block_id(x[p] = y)].add(y);
int ans = 0;
for(int i = 0, start = -1; i <= max_block_id; i++){
auto [cnt, next_start] = ds[i].get(start);
ans += cnt;
start = next_start;
}
return ans;
}
