#include <bits/stdc++.h>
using namespace std;
int t=500;
int n,L,m;
int b[150000];
int c[150000];
struct A{
int x,cnt,nxt,idx;
};
vector<A> a[400];
int C;
void init(){
int i,j;
for(i=0 ; i<n ; i++)c[i]=b[i];
sort(c,c+n);
for(i=0 ; i<=(n-1)/t ; i++)a[i].clear();
for(i=0 ; i<n ;i++)
a[i/t].push_back({c[i],0,0});
for(i=(n-1)/t ; i>=0 ; i--){
for(j=(int)a[i].size()-1 ; j>=0 ; j--){
if(a[i][j].x+L>=a[i].rbegin()->x){
a[i][j].nxt=a[i][j].x+L;
a[i][j].cnt=1;
}
else{
auto k=upper_bound(a[i].begin(),a[i].end(),(A){a[i][j].x+L,0,0},[&](A q,A w){
return q.x<w.x;
});
a[i][j].cnt=k->cnt+1;
a[i][j].nxt=k->nxt;
}
}
}
}
void del(int x,int y){
for(int i=0 ; i<a[x].size() ; i++){
if(a[x][i].x==y){
a[x].erase(a[x].begin()+i);
break;
}
}
for(int i=(int)a[x].size()-1 ; i>=0 ; i--){
if(a[x][i].x+L>=a[x].rbegin()->x){
a[x][i].nxt=a[x][i].x+L;
a[x][i].cnt=1;
}
else{
auto k=upper_bound(a[x].begin(),a[x].end(),(A){a[x][i].x+L,0,0},[&](A q,A w){
return q.x<w.x;
});
a[x][i].cnt=k->cnt+1;
a[x][i].nxt=k->nxt;
}
}
}
void add(int x,int y){
for(int i=0 ; i<=a[x].size() ; i++){
if(i==a[x].size() || a[x][i].x>=y ){
a[x].insert(a[x].begin()+i,{y,0,0});
break;
}
}
for(int i=(int)a[x].size()-1 ; i>=0 ; i--){
if(a[x][i].x+L>=a[x].rbegin()->x){
a[x][i].nxt=a[x][i].x+L;
a[x][i].cnt=1;
}
else{
auto k=upper_bound(a[x].begin(),a[x].end(),(A){a[x][i].x+L,0,0},[&](A q,A w){
return q.x<w.x;
});
a[x][i].cnt=k->cnt+1;
a[x][i].nxt=k->nxt;
}
/// cout<<C<<" "<<a[x][i].x<<" "<<a[x][i].nxt<<" "<<a[x][i].cnt<<endl;
}
}
int f(){
int x=-2e9;
int ans=0;
for(int i=0 ; i<=(n-1)/t ; i++){
if(a[i].size()==0 || x>=a[i].rbegin()->x)continue;
auto k=upper_bound(a[i].begin(),a[i].end(),(A){x,0,0},[&](A q, A w){
return q.x<w.x;
});
ans+=k->cnt;
x=k->nxt;
/// cout<<x<<" "<<ans<<"!\n";
}
return ans;
}
int g(int x){
int k=-1;
for(int i=0 ; i<=(n-1)/t ; i++){
if (x<=a[i].rbegin()->x ){
k=i;
break;}
}
if(k>=0)return k;
return (n-1)/t;
}/*
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>L>>m;
int i;
for(i=0 ; i<n ; i++)cin>>b[i];
for(i=0 ; i<m ; i++)
{
if(i%(t-1)==0)init();
int x,y;
cin>>x>>y;
del(g(b[x]),b[x]);
add(g(y),y);
b[x]=y;
cout<<f()<<"\n";
}
return 0;
}*/
#include "elephants.h"
void init(int N, int l, int X[])
{
L=l;
n=N;
for(int i=0 ; i<N ; i++)b[i]=X[i];
}
int update(int i, int y)
{
if(C%(t-1)==0)init();
C++;
del(g(b[i]),b[i]);
add(g(y),y);
b[i]=y;
return f();
}
