#include "elephants.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second
mt19937 rng(998244353);
const int N=2e5+5;
int a[N];
int b[N];
const int K=400;
int block[K][2*K];
int nxt[K][2*K];
int val[K][2*K];
int sz[K];
pi go[K][2*K];
int n,len;
void make(int i) {
int R=0;
for (int L=0; L<sz[i]; ++L) {
while (R<sz[i] && block[i][R]-block[i][L]<=len) ++R;
nxt[i][L]=R;
val[i][L]=block[i][L]+len;
}
for (int j=sz[i]-1; j>=0; --j) {
if (nxt[i][j]==sz[i]) {
go[i][j]={1,val[i][j]};
} else {
go[i][j]={go[i][nxt[i][j]].f+1,go[i][nxt[i][j]].s};
}
}
}
void build() {
n=0;
forn(i,K) {
forn(j,sz[i]) b[n++]=block[i][j];
}
for(int l=0; l<n; l+=K) {
int r=min(l+K,n);
sz[l/K]=r-l;
for(int i=l; i<r; ++i) {
block[l/K][i-l]=b[i];
}
int i=l/K;
make(i);
}
}
void init(int _n, int _l, int x[]) {
n=_n; len=_l;
forn(i,n) a[i]=x[i];
forn(i,n) b[i]=a[i];
sort(b,b+n);
for(int l=0; l<n; l+=K) {
int r=min(l+K,n);
sz[l/K]=r-l;
for(int i=l; i<r; ++i) {
block[l/K][i-l]=b[i];
}
}
build();
}
void rem(int i, int x) {
forn(j,sz[i]) {
if (block[i][j]<x) continue;
block[i][j]=block[i][j+1];
}
--sz[i];
make(i);
}
void del(int x) {
for (int i=0; i<K; ++i) {
if (x<=block[i][sz[i]-1]) {
rem(i,x);
break;
}
}
}
void insert(int i, int x) {
int z=1;
int t=x;
forn(j,sz[i]) {
if (block[i][j]<x) continue;
swap(t,block[i][j]);
}
block[i][sz[i]]=t;
++sz[i];
make(i);
}
void add(int x) {
for (int i=0; i<K; ++i) {
if (x<=block[i][sz[i]-1]) {
insert(i,x);
break;
}
if (i==(n-1)/K) {
insert(i,x);
break;
}
}
}
int Q=0;
int update(int ind, int x) {
del(a[ind]);
a[ind]=x;
add(a[ind]);
++Q;
if (Q==K) {
Q=0;
build();
}
//forn(i,n) {
// if (!sz[i]) break;
// forn(j,sz[i]) cout<<block[i][j]<<' '; cout<<'\n';
// forn(j,sz[i]) cout<<nxt[i][j]<<' '; cout<<'\n';
// forn(j,sz[i]) cout<<val[i][j]<<' '; cout<<'\n';
// forn(j,sz[i]) cout<<go[i][j].f<<','<<go[i][j].s<<" "; cout<<'\n';
//}
int i=0, j=0, pos=block[0][0];
int ans=0;
for (;sz[i];) {
auto it = go[i][j];
ans += it.f;
pos = it.s;
while (sz[i] && block[i][sz[i]-1]<=pos) ++i;
if (!sz[i]) break;
int l=0, r=sz[i]-1;
while (l<r) {
int m=(l+r)>>1;
if (block[i][m]<=pos) l=m+1;
else r=m;
}
j=r;
}
return ans;
}
