#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
const int sqr=400;
int tam[sqr];
struct node{
int x,vai,resp;
};
node dp[sqr][2*sqr];
vector<int> vec;
int m;
int n;
void updbl(int bloco){
auto &d=dp[bloco];
R(i,tam[bloco]-1,0){//mudar pra 2pointer
if(d[tam[bloco]-1].x<=d[i].x+m){
d[i].vai=d[i].x+m;
d[i].resp=1;
}
else{
int r=tam[bloco]-1;
int l=i+1;
int vai=i;
while(l<=r){
int mid=(l+r)/2;
if(d[mid].x<=d[i].x+m){
vai=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
vai++;
d[i].vai=d[vai].vai;
d[i].resp=d[vai].resp;
d[i].resp++;
}
}
}
void bota(int id,int pos,int bloco){
R(i,tam[bloco]-1,pos)dp[bloco][i+1]=dp[bloco][i];
tam[bloco]++;
dp[bloco][pos].x=id;
updbl(bloco);
}
void tira(int pos, int bloco){
L(i,pos,tam[bloco]-1)dp[bloco][i]=dp[bloco][i+1];
tam[bloco]--;
updbl(bloco);
}
pair<int,int> find(int val){
int l=0;
int r=399;
int blocat=0;
while(l<=r){
int mid=(l+r)/2;
if(tam[mid]==0 || dp[mid][0].x>val){
r=mid-1;
}
else{
blocat=mid;
l=mid+1;
}
}
l=0;
r=tam[blocat]-1;
int ret=-1;
while(l<=r){
int mid=(l+r)/2;
if(dp[blocat][mid].x<=val){
ret=mid;
l=mid+1;
}
else r=mid-1;
}
return {blocat,ret};
}
int calc(){
int idat=0;
int bloc=0;
int resp=0;
while(true){
int vai=dp[bloc][idat].vai;
resp+=dp[bloc][idat].resp;
bloc++;
while(bloc<sqr){
if(tam[bloc]==0)return resp;
if(dp[bloc][tam[bloc]-1].x>vai)break;
bloc++;
}
int l=0;
int r=tam[bloc]-1;
int nid=-1;
while(l<=r){
int mid=(l+r)/2;
if(dp[bloc][mid].x<=vai){
l=m+1;
nid=mid;
}else{
r=mid-1;
}
}
nid++;
//resp++;
}
}
void ini(){
int pat=0;
L(i,0,sqr-1){
L(j,0,tam[i]-1){
vec[pat++]=dp[i][j].x;
}
tam[i]=0;
}
L(i,0,n-1){
dp[i/sqr][i%sqr].x=vec[i];
tam[i/sqr]++;
}
}
vector<int> arr;
void init(int N, int M, int X[])
{
n=N;m=M;
vec.resize(n);
L(i,0,n-1)vec[i]=X[i];
arr=vec;
sort(all(vec));
L(i,0,n-1){
dp[i/sqr][i%sqr].x=vec[i];
tam[i/sqr]++;
}
}
int cnt=0;
int update(int i, int y)
{
auto [bl,id]=find(arr[i]);
arr[i]=y;
tira(id,bl);
auto [bl2,id2]=find(arr[i]);
bota(arr[i],id2+1,bl2);
//L(i,0,4)cout<<dp[0][i].x<<" ";
//cout<<"\n";
if(cnt==sqr-4){
ini();
cnt=0;
}
return calc();
}
