#include "elephants.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int MAXN = 150000, BS = 400, INF = 1e9 + 7;
int n, w, p[MAXN], ps[MAXN], buck[MAXN];
vector< pair< int, int > > bl[MAXN / BS + 3];
int dp1[MAXN], dp2[MAXN];
void trick(vector< pair<int, int> > &cur, pair<int, int> val, bool keep){
stack< pair<int, int> > tmp;
while(!cur.empty()){
if(keep){
if(cur.back() < val){
cur.push_back(val);
break;
}
}
else{
if(val == cur.back()){
cur.pop_back();
break;
}
}
tmp.push(cur.back()), cur.pop_back();
}
if(keep && cur.empty())
cur.push_back(val);
while(!tmp.empty())
cur.push_back(tmp.top()), tmp.pop();
sort(cur.begin(), cur.end());
}
void upd(int id){
for(int i = (int)bl[id].size() - 1, j = (int)bl[id].size();i >= 0;i--){
int me = bl[id][i].Y, pos = bl[id][i].X;
buck[me] = id;
while(j - 1 >= i && bl[id][j - 1].X > pos + w) j--;
if(j == (int)bl[id].size()) dp1[me] = 1, dp2[me] = pos + w;
else dp1[me] = dp1[bl[id][j].Y] + 1, dp2[me] = dp2[bl[id][j].Y];
}
}
void build(){
for(int i = 0, j = 0;i < n;i += BS, j++)
bl[j].clear();
for(int i = 0, j = 0, z = 1;i < n;i++, (z == BS ? z = 1, j++: z++))
bl[j].push_back(MP(p[ps[i]], ps[i]));
for(int i = 0, j = 0;i < n;i += BS, j++)
upd(j);
}
void init(int N, int L, int X[]){
n = N, w = L;
for(int i = 0;i < n;i++)
p[i] = X[i], ps[i] = i;
sort(ps, ps + n, [](int x, int y){return p[x] < p[y];});
build();
}
int solve(){
int cnt = 0, pos = 0;
for(int j = 0;;j++){
if(bl[j].empty())
break;
else if(bl[j].back().X < pos)
continue;
pair<int, int> tmp = *upper_bound(bl[j].begin(), bl[j].end(), MP(pos, -1));
cnt += dp1[tmp.Y], pos = dp2[tmp.Y] + 1;
}
return cnt;
}
int cntQ;
int update(int i, int y){
cntQ++;
if(cntQ == BS){
trick(bl[buck[i]], MP(p[i], i), 0), upd(buck[i]);
p[i] = y, cntQ = 0;
for(int j = 0, it = 0;it < n;j++){
if(j * BS > n){
ps[n - 1] = i;
break;
}
for(pair<int, int> v: bl[j]){
if(i != -1 && MP(p[i], i) < v)
ps[it++] = i, i = -1;
ps[it++] = v.Y;
}
}
build();
}
else{
trick(bl[buck[i]], MP(p[i], i), 0), upd(buck[i]);
p[i] = y;
for(int j = 0;;j++){
int left = (j ? bl[j - 1].back().X: 0), right = (bl[j + 1].empty() ? INF: bl[j + 1][0].X);
if(left <= y && y <= right){
trick(bl[j], MP(p[i], i), 1), upd(j);
break;
}
}
}
return solve();
}
