#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define big __int128_t
#define ll long long
#define endl '\n'
#define Endl '\n'
#define fio ios::sync_with_stdio(0); cin.tie(0);
#define fi first
#define se second
#define pii pair<int,int>
#define arr vector<int>
#define parr vector<pii>
#define check cout<<'e'<<endl<<flush;
#define append push_back
#define all(v) v.begin(),v.end()
int n,l,m;
arr a;
set<pii> s;
arr nxt,cnt;
arr buc;
vector<arr> buk;
arr st;
const int sz=600;
void init(int N,int L,int X[])
{
n=N;
l=L;
a.resize(n);
for (int i=0;i<n;i++) a[i]=X[i];
nxt.resize(n);
cnt.resize(n);
buc.resize(n);
parr c;
for (int i=0;i<n;i++)
{
c.append({a[i],i});
s.insert({a[i],i});
}
st.resize(1010);
for (int i=0;i<1010;i++)
{
st[i]=1234567890;
}
buk.resize(1010);
s.insert({1234567890,-1});
int t=sz,b=-1;
for (int i=0;i<n;i++)
{
int now=c[i].fi,idx=c[i].se;
t++;
if (t>=sz)
{
t=0;
b++;
st[b]=now;
}
buc[idx]=b;
buk[b].append(idx);
}
for (int i=n-1;i>=0;i--)
{
int nw=c[i].fi,idx=c[i].se;
auto now=*s.upper_bound({nw+l,12341234});
if (now.se==-1)
{
nxt[idx]=nw+l;
cnt[idx]=1;
}
else if (buc[now.se]==buc[idx])
{
nxt[idx]=nxt[now.se];
cnt[idx]=cnt[now.se]+1;
}
else
{
nxt[idx]=nw+l;
cnt[idx]=1;
}
}
}
void upd(int b)
{
arr p;
for (int i:buk[b]) if (buc[i]==b) p.append(i);
sort(all(p),[&](const int &i,const int &j){
if (a[i]==a[j]) return i<j;
return a[i]>a[j];
});
if (p.empty()) return;
int r=-1;
int nn=p.size();
for (int i:p)
{
int nw=a[i],idx=i;
while (r+1<nn && a[p[r+1]]>a[i]+l) r++;
pii now={0,0};
if (r==-1) now.se=-1;
else now.se=p[r];
// cout<<"upd: "<<endl;
// cout<<nw<<' '<<idx<<' '<<now.fi<<' '<<now.se<<endl<<flush;
if (now.se==-1)
{
nxt[idx]=nw+l;
cnt[idx]=1;
}
else if (buc[now.se]==buc[idx])
{
nxt[idx]=nxt[now.se];
cnt[idx]=cnt[now.se]+1;
}
else
{
nxt[idx]=nw+l;
cnt[idx]=1;
}
}
}
void buc_upd();
int qcnt=0;
int update(int idx,int c)
{
int bef,befb;
bef=a[idx];
befb=buc[idx];
int nxb=distance(st.begin(),upper_bound(all(st),c))-1;
nxb=max(0ll,(ll)nxb);
if (befb!=nxb) buk[nxb].append(idx);
a[idx]=c;
buc[idx]=nxb;
s.erase({bef,idx});
s.insert({c,idx});
upd(befb);
upd(nxb);
pii now=*s.begin();
int t=0;
while (now.se!=-1)
{
t+=cnt[now.se];
// cout<<now.fi<<' '<<now.se<<' '<<t<<endl<<flush;
now=*s.upper_bound({nxt[now.se],12341234});
// cout<<"next: "<<now.fi<<' '<<now.se<<endl<<flush;
}
qcnt++;
if (qcnt%300==0) buc_upd();
return t;
}
void buc_upd()
{
arr p;
int t=sz,b=-1;
for (int i=0;i<1010;i++)
{
buk[i].clear();
st[i]=1234567890;
}
for (pii i:s)
{
int now=i.fi,idx=i.se;
if (idx==-1) continue;
// cout<<now<<' '<<idx<<endl<<flush;
p.append(idx);
t++;
if (t>=sz)
{
t=0;
b++;
st[b]=now;
}
buc[idx]=b;
buk[b].append(idx);
nxt[idx]=0;
cnt[idx]=0;
}
reverse(all(p));
int r=-1;
for (int i:p)
{
// auto now=*s.upper_bound({a[i]+l,12341234});
while (r+1<n && a[p[r+1]]>a[i]+l) r++;
pii now={a[p[r]],0};
if (r==-1) now.se=-1;
else now.se=p[r];
int idx=i;
// cout<<"upd: "<<endl;
// cout<<i.fi<<' '<<i.se<<' '<<now.fi<<' '<<now.se<<endl<<flush;
if (now.se==-1)
{
nxt[idx]=a[i]+l;
cnt[idx]=1;
}
else if (buc[now.se]==buc[idx])
{
nxt[idx]=nxt[now.se];
cnt[idx]=cnt[now.se]+1;
}
else
{
nxt[idx]=a[i]+l;
cnt[idx]=1;
}
}
}
