#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int s1=300;
const int s2=500;
const int s3=500;
const int maxn=150001;
int n,l;
int x[maxn];
set<int> s[s2];
void init(int N, int L, int X[])
{
n=N;
l=L;
for(int i=0; i<n; i++)
x[i]=X[i];
}
unordered_map<int,int> cnt,id,in;
void rebuild()
{
vector<int> v;
for(int i=0;i<n;i++)
{
in[x[i]]++;
if(in[x[i]]==1)
v.push_back(x[i]);
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i+=s1)
{
for(int j=0;j<s1;j++)
{
if(i+j>=v.size())break;
//cout<<"|>"<<v[i+j]<<endl;
s[i/s1].insert(v[i+j]);
}
}
}
void build(int i)
{
auto it=s[i].end();
while(it!=s[i].begin())
{
it--;
int h=*it+l;
auto it1=s[i].upper_bound(h);
if(it1==s[i].end())
{
cnt[*it]=1;
id[*it]=*it;
}
else
{
cnt[*it]=cnt[*it1]+1;
id[*it]=id[*it1];
}
}
}
int fb(int y)
{
for(int i=0;i<s2-1;i++)
{
if(s[i].size()==0)continue;
auto it=s[i].end();
it--;
if(y<=*it)return i;
}
return s2-1;
}
int num=0;
int update(int i, int y)
{
num++;
if(num%s3==1)
{
x[i]=y;
for(int j=0;j<s2;j++)
s[j].clear();
cnt.clear();
id.clear();
in.clear();
rebuild();
/*cout<<"*"<<endl;
for(int i=0;i<s2;i++)
{
for(auto it=s[i].begin();it!=s[i].end();it++)
cout<<*it<<" ";
cout<<endl;
}
cout<<"="<<endl;*/
for(int i=0;i<s2;i++)
build(i);
}
else
{
int b1=fb(x[i]);
if(in[x[i]]==1)s[b1].erase(x[i]);
in[x[i]]--;
in[y]++;
int b2=fb(y);
s[b2].insert(y);
x[i]=y;
//cout<<"-- "<<b1<<" "<<b2<<endl;
build(b1);
build(b2);
}
int ans=0,c=-1;
for(int i=0;i<s2;i++)
{
auto it=s[i].upper_bound(c);
if(it==s[i].end())continue;
//cout<<*it<<" "<<cnt[*it]<<" "<<id[*it]<<endl;
ans+=cnt[*it];
c=id[*it]+l;
}
//cout<<"!! "<<ans<<endl;
return ans;
}
