#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int sz=40;
int b[150001][55];
multiset<int> s;
int l;
int p[150001];
int id=1;
void init(int N, int L, int X[])
{
l=L;
for(int i=0;i<N;i++)
{
s.insert(X[i]);
p[i]=X[i];
}
/*auto it=s.end();
for(int i=N-1;i>=0;i--)
{
it--;
mp[*it]=i;
int x=N-2*i+1;
for(int j=x+1;j<=sz;j++)
b[i][j]=1e9;
auto it1=s.lower_bound(*it+L);
it1++;
if(it1==s.end()||mp[*it1]-i+1>=sz)
{
for(int j=1;j<=x;j++)
b[i][j]=1;
continue;
}
int y=mp[*it1];
y=mp[y];
}*/
}
map<int,int> mp,r;
int update(int i, int y)
{
int pr=p[i];
id++;
s.erase(s.find(p[i]));
s.insert(y);
p[i]=y;
int ans=0,z=0;
vector<int> g;
auto it=s.begin();
while(it!=s.end())
{
int x=*it+l;
//cout<<*it<<" ";
if(mp[*it]==id-1&&*it>y&&*it>pr)
{
//cout<<"in "<<endl;
z=r[*it];
break;
}
g.push_back(*it);
ans++;
it=s.upper_bound(x);
}
//cout<<endl;
int curr=z;
for(int i=g.size()-1;i>=0;i--)
{
curr++;
mp[g[i]]=id;
r[g[i]]=curr;
}
return ans;
}
