#include "elephants.h"
#include <bits/stdc++.h>
#include <set>
#define MP make_pair
#pragma GCC optimize("Os")
using namespace std;
const int N = 1e5 + 30;
int n, l;
set <pair<int, int> > fp;
int x[N], fr, sc;
int haj[N], nax[N], h[N];
void rmv(int i)
{
bool bl = 0;
if(i != fr && i != sc)
{
nax[haj[i]]= nax[i];
haj[nax[i]] = haj[i];
bl = 1;
}
fp.erase(MP(x[i], i));
auto i1 = fp.end();
fr = (*fp.begin()).second, sc = (*(--i1)).second;
if(bl)
{
int v = i;
while(v != fr)
{
v = nax[v];
if(x[v] + l < x[nax[i]]) break;
if(x[v] + l < x[haj[i]]) h[v] = haj[i];
}
}
}
void add(int i)
{
auto i1 = fp.lower_bound(MP(x[i], i));
if(i1 != fp.end()) nax[(*i1).second] = i, haj[i] = (*i1).second;
if(i1 != fp.begin()) haj[(*(--i1)).second] = i, nax[i] = (*i1).second;
fp.insert(MP(x[i], i));
i1 = fp.end();
fr = (*fp.begin()).second, sc = (*(--i1)).second;
i1 = fp.lower_bound(MP(x[i] + l + 1, -1));
if(i1 != fp.end()) h[i] = (*i1).second;
int v = i;
while(v != fr)
{
v = nax[v];
if(x[v] + l < x[nax[i]]) break;
if(x[v] + l < x[i]) h[v] = i;
}
}
int go()
{
int v = fr, sm = 1, nx = x[fr] + l;
while(nx < x[sc])
{
sm++; v = h[v]; nx = x[v] + l;
}
return sm;
}
void init(int N, int L, int X[])
{
n=N, l=L;
for(int i = 0; i < n; i++)
{
x[i] = X[i];
add(i);
}
}
int update(int i, int y)
{
rmv(i);
x[i] = y;
add(i);
return go();
}
