#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int BUC = 1;
const int CNT_BUC = 400;
const int RECALC_TIME = 1;
int n,L;
int a[150005];
struct bucket
{
vector<int> v;
int cnt[BUC+RECALC_TIME+5],ri[BUC+RECALC_TIME+5];
void calc_dp()
{
assert((int)v.size() < BUC + RECALC_TIME + 5);
sort(v.begin(),v.end());
int poz = (int)v.size();
for(int i=(int)v.size()-1;i>=0;i--)
{
while(poz-1>=0 && v[poz-1] > v[i] + L)
poz--;
if(poz == (int)v.size())
{
cnt[i] = 1;
ri[i] = v[i] + L;
}
else
{
cnt[i] = cnt[poz] + 1;
ri[i] = ri[poz];
}
}
}
void init(vector<int> aux)
{
v = aux;
calc_dp();
}
void baga(int x)
{
v.push_back(x);
calc_dp();
}
void scoate(int x)
{
bool gasit=0;
for(int i=0;i<v.size();i++)
{
if(v[i]==x)
{
v.erase(v.begin()+i);
gasit=1;
break;
}
}
assert(gasit);
calc_dp();
}
pair<int,int> get(int le)
{
int pozle = upper_bound(v.begin(),v.end(),le) - v.begin();
if(pozle == (int)v.size())
return {0,le};
return {cnt[pozle], ri[pozle]};
}
};
bucket buckets[CNT_BUC+5];
pair<int,int> ord[150005];
int unde[150005];
int caple[CNT_BUC+5],cntb;
void calc_all()
{
for(int i=0;i<n;i++)
ord[i] = {a[i], i};
sort(ord,ord+n);
cntb=0;
for(int le=0;le<n;le+=BUC)
{
int ri = min(le+BUC-1, n-1);
vector<int> aux;
for(int i=le;i<=ri;i++)
{
aux.push_back(ord[i].first);
unde[ord[i].second] = cntb;
}
caple[cntb] = le;
buckets[cntb].init(aux);
cntb++;
}
}
void init(int N, int citL, int X[])
{
n = N;
L = citL;
for(int i=0;i<n;i++)
a[i] = X[i];
calc_all();
}
int update_cnt;
int update(int i, int y)
{
buckets[unde[i]].scoate(a[i]);
a[i] = y;
unde[i] = -1;
for(int b=0;b<cntb;b++)
{
if(b==cntb-1 || caple[b+1] > a[i])
{
unde[i] = b;
break;
}
}
assert(unde[i]!=-1);
buckets[unde[i]].baga(a[i]);
update_cnt++;
if(update_cnt % RECALC_TIME == 0)
{
calc_all();
}
assert(cntb>0);
pair<int,int> aux = buckets[0].get(-INF);
int cnt = aux.first, le = aux.second;
//cerr<<cnt<<" "<<le<<" dupa 0\n";
for(int i=1;i<cntb;i++)
{
aux = buckets[i].get(le);
cnt += aux.first;
le = aux.second;
//cerr<<aux.first<<" "<<aux.second<<" aux "<<i<<"\n";
}
return cnt;
}
