#include <bits/stdc++.h>
#define lb(a, x) lower_bound(begin(a), end(a), x)
using namespace std;
constexpr int MX=150000, B=448, C=(MX+B-1)/B;
struct iii { int x, n, y; };
bool operator<(const iii& a, int b) { return a.x<b; }
bool operator<(int a, const iii& b) { return a<b.x; }
int A[MX], X[MX], N, M, Q;
vector<iii> D[C];
void calc_bucket(vector<iii>& v) {
for(int n=v.size(), i=n, p=n; i--;) {
while(p && v[i].x<v[p-1].x-M) p--;
if(p==n) v[i].n=1, v[i].y=v[i].x+M;
else v[i].n=v[p].n+1, v[i].y=v[p].y;
}
}
void init_buckets() {
int k=0;
for(auto&v:D) {
for(auto[x,n,y]:v) X[k++]=x;
v.clear();
}
for(int i=0, j=0; i<N;) {
D[j].push_back({X[i], 0, 0});
if(++i%B==0 || i==N) calc_bucket(D[j++]);
}
}
void del(int x) {
for(auto&v:D) if(v.size() && v.front().x<=x && x<=v.back().x) {
v.erase(lb(v, x));
calc_bucket(v);
break;
}
}
void add(int x) {
int p=0, n=N-1;
for(auto&v:D) if(!(n-=v.size()) || v.size() && p<=x && x<=(p=v.back().x)) {
v.insert(lb(v, x), {x, 0, 0});
calc_bucket(v);
break;
}
}
int answer() {
int p=0, n=0;
for(auto&v:D) if(v.size() && p<=v.back().x) {
auto[x,m,y]=*lb(v, p);
n+=m, p=y+1;
}
return n;
}
void init(int n, int m, int E[]) {
N=n, M=m;
for(int i=0; i<C; i++) D[i].reserve(B);
for(int i=0; i<N; i++) D[i/B].push_back({A[i]=E[i], 0, 0});
}
int update(int n, int x) {
if(Q++%B==0) init_buckets();
del(A[n]);
add(A[n]=x);
return answer();
}
