#include "elephants.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
// general
ll range;
vector<ll> x;
unordered_map<ll, ll> m;
// SQRT Data Structure
ll const blksz = 300;
ll blk;
vector<vector<ll> > groups;
vector<vector<pi> > dp;
ll query()
{
//show(4);
ll ret = 0;
ll last = -1;
for (ll i=0; i<blk; ++i)
{
if (groups[i].empty() || groups[i].back()<=last) continue;
ll ind = ub(groups[i].begin(), groups[i].end(), last)-groups[i].begin();
ret+=dp[i][ind].f;
last = dp[i][ind].s;
}
return ret;
}
void processblk(ll ind)
{
//show(3);
if (groups[ind].empty()) return;
ll n= groups[ind].size();
dp[ind].clear();
dp[ind].resize(n);
ll r = n-1;
for (ll l = n-1; l>=0; --l)
{
while (groups[ind][r]-groups[ind][l]>range) {r--;}
if (r==n-1) dp[ind][l] = mp(1, groups[ind][l] + range);
else dp[ind][l] = dp[ind][r+1], dp[ind][l].f++;
}
}
void remove(ll pos)
{
//show(1);
ll i;
for (i=0; i<blk; ++i)
{
if (groups[i].empty()) continue;
if (groups[i][0]<=pos && groups[i].back()>=pos) break;
}
groups[i].erase(lb(groups[i].begin(), groups[i].end(), pos));
processblk(i);
}
void insert(ll pos)
{
//show(1);
ll i;
for (i=0; i<blk; ++i)
{
if (groups[i].empty()) continue;
if (groups[i][0]>=pos) break;
}
if (i) i--;
groups[i].insert(ub(groups[i].begin(), groups[i].end(), pos), pos);
if (groups[i].size()>=2*blksz)
{
vector<ll> neww;
vector<pi> emp;
ll half = groups[i].size()/2;
while (half--) {neww.pb(groups[i].back()); groups[i].pop_back();}
reverse(neww.begin(), neww.end());
groups.insert(groups.begin()+i+1, neww);
dp.insert(dp.begin()+i+1, emp);
processblk(i);
processblk(i+1);
blk++;
}
else {processblk(i);}
}
void init(int N, int L, int X[])
{
sort(X, X+N);
range = L;
x.resize(N);
blk = (N-1)/blksz + 1;
groups.resize(blk);
dp.resize(blk);
for (ll i=0; i<N; ++i)
{
m[X[i]]++;
if (m[X[i]]==1) groups[i/blksz].pb(X[i]);
}
for (ll i=0; i<blk; ++i) processblk(i);
for (ll i=0; i<N; ++i) x[i] = X[i];
}
int update(int i, int y)
{
//show("FUCK");
m[x[i]]--; m[y]++;
if (m[x[i]]==0) remove(x[i]);
if (m[y]==1) insert(y);
x[i] = y;
return query();
}
