#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 15e4+5, sqr = 390;
int n, pos[MAXN], cnt = 0, seg[MAXN], l, last = 0;
vector <pair<int,int>> dp[sqr];
vector <int> all[sqr];
multiset <pair<int,int>> el;
void init(int N, int L, int X[]){
n = N; l = L;
for(int i = 0; i < n; i++){
pos[i] = X[i];
//el.insert({pos[i], i});
}
}
void caldp(int ind){
for(int i = 0; i < (int)all[ind].size(); i++) dp[ind].push_back({0,0});
for(int i = (int)all[ind].size()-1; i>=0; i--){
int id = upper_bound(all[ind].begin(), all[ind].end(), all[ind][i]+l) - all[ind].begin();
if(id >= (int)all[ind].size()){
dp[ind][i].first = 1; dp[ind][i].second = all[ind][i]+l+1;
continue;
}
dp[ind][i].first = dp[ind][id].first+1; dp[ind][i].second = dp[ind][id].second;
}
return;
}
void build(){
// cout << "build!!" << endl;
el.clear();
vector <pair<int,int>> pts;
for(int i = 0; i < n; i++) pts.push_back({pos[i], i});
for(int i = 0; i < last; i++) all[i].clear(), dp[i].clear();
sort(pts.begin(), pts.end());
int pt = 0, c = 0;
while(pt < n){
while(pt < n && (int)all[c].size() < sqr){
all[c].push_back(pts[pt].first);
seg[pts[pt].second] = c; pt++;
}
caldp(c);
c++;
}
last = c;
for(int i = 0; i < n; i++) el.insert({pos[i], seg[i]});
return;
}
void del(int ind, int val){
vector <int> tmp;
while(all[ind].back() != val){
tmp.push_back(all[ind].back());
all[ind].pop_back();
}
all[ind].pop_back();
while(!tmp.empty()){
all[ind].push_back(tmp.back());
tmp.pop_back();
}
dp[ind].clear(); caldp(ind);
return;
}
void add(int ind, int val){
vector <int> tmp;
while(!all[ind].empty() && all[ind].back() > val){
tmp.push_back(all[ind].back());
all[ind].pop_back();
}
all[ind].push_back(val);
while(!tmp.empty()){
all[ind].push_back(tmp.back());
tmp.pop_back();
}
dp[ind].clear(); caldp(ind);
return;
}
int get(){
int cur = el.begin()->first, res = 0;
while(cur <= el.rbegin()->first){
int ind = el.lower_bound({cur,0})->second;
int id = lower_bound(all[ind].begin(), all[ind].end(), cur) - all[ind].begin();
res += dp[ind][id].first; cur = dp[ind][id].second;
}
return res;
}
int update(int i, int y){
if(cnt % 387 == 0) build();
del(seg[i],pos[i]);
auto it = el.lower_bound({pos[i],seg[i]});
el.erase(it);
int pt = el.rbegin()->second;
it = el.lower_bound({y,0});
if(it != el.end()) pt = it->second;
add(pt, y); el.insert({y, pt});
seg[i] = pt; pos[i] = y;
int ans = get(); cnt++;
return ans;
}
