#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int B_QTD = 120, B_SZ = 1255, Q = 400, MAXN = 150010;
int n, L, q_cnt;
int photo[MAXN], ult_coberto[MAXN], posicao[MAXN], myb[MAXN];
set<pair<int, int>> eleph_in_order; //{posicao, id}
vector<int> buckets[B_QTD]; //id dos elephante ordenandas dividas nos buckets
int get_bucket(int i){
return i/B_SZ;
}
void make_bucket(vector<int> &v){
if(v.empty()) return;
for(int l = v.size()-1, r = v.size(); l >= 0; l--){
while( posicao[ v[l] ] + L < posicao[ v[r-1] ]) r--;
if(r == (int)v.size()){//caso eu cobro tudo mundo
photo[ v[l] ] = 1;
ult_coberto[ v[l] ] = posicao[ v[l] ]+L;
}
else{
photo[ v[l] ] = 1+photo[ v[r] ];
ult_coberto[ v[l] ] = ult_coberto[ v[r] ];
}
}
}
void assign_buckets(){
for(int i = 0; i < B_QTD; i++) buckets[i].clear();
int i = 0;
for(auto it = eleph_in_order.begin(); it != eleph_in_order.end(); ++it, ++i){
int id = it->second;
myb[id] = get_bucket(i);
buckets[myb[id]].push_back(id);
}
for(int i = B_QTD; i >= 0; i--) make_bucket(buckets[i]);
}
int find_answer(){
int ans = 0;
int i = 0, j = 0;
while(i < B_QTD){
if(buckets[i].empty()){
i++;
continue;
}
int no = buckets[i][j];
ans += photo[no];
int uc = ult_coberto[no];
int li = 0;
for(; i < B_QTD; i++){
if(buckets[i].empty()) continue;
if(posicao[ buckets[i][0] ] <= uc) li = i;
if(posicao[ buckets[i].back() ] > uc) break;
}
j = 0;
for(int k = 11; k >= 0; k--){//cada buckets tem maximo 1250 elefantes
if(j + (1<<k) >= (int)buckets[li].size()) continue;
if( posicao[ buckets[li][j+(1<<k)] ] <= uc ) j += (1<<k);
}
j++; //j:= quem eu n consigo pegar
if(j >= (int)buckets[li].size()){
j = 0;
i = li+1;
}
}
return ans;
}
void init(int N, int _L, int X[]){
n = N;
L = _L;
for(int i = 0; i < n; i++){
posicao[i] = X[i];
eleph_in_order.insert({X[i], i});
}
assign_buckets();
}
int update(int i, int y){
q_cnt++;
int pos0 = posicao[i];
posicao[i] = y;
eleph_in_order.erase({pos0, i});
eleph_in_order.insert({y, i});
if(q_cnt == Q){
assign_buckets();
q_cnt = 0;
}
else{
vector<int> &antigo = buckets[ myb[i] ];
int id = 0;
while(id < (int)antigo.size() && antigo[id] != i) id++;
antigo.erase(antigo.begin()+id);
make_bucket(antigo);
auto frente_de_mim = eleph_in_order.upper_bound({y, i});
if(frente_de_mim == eleph_in_order.end()) --frente_de_mim, --frente_de_mim;
myb[i] = myb[frente_de_mim->second];
vector<int> &novo = buckets[ myb[i] ];
id = 0;
while(id < (int)novo.size() && posicao[ novo[id] ] < y) id++;
novo.insert(novo.begin()+id, i);
make_bucket(novo);
}
return find_answer();
}
