// M
#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;
typedef long long ll;
const int N = 151234, SQ = 700, QS = N / SQ + 4, SCALE = N * 3;
int n, nsq, lzcnt, EXTRAS, B[N];
ll k, X[N];
vector < ll > V[QS];
vector < pair < int , ll > > dp[QS];
inline void Build(int block)
{
int sz = (int)V[block].size();
assert(sz >= 1); // For convenience.
dp[block].resize(sz);
int r = sz;
for (int i = sz - 1; i >= 0; i --)
{
while (V[block][r - 1] > V[block][i] + k)
r --;
if (r < sz)
dp[block][i] = {dp[block][r].first + 1, dp[block][r].second};
else
dp[block][i] = {1, V[block][i] + k};
}
}
inline void Erase(int block, ll val)
{
for (int i = 0; i < (int)V[block].size(); i ++)
if (V[block][i] == val)
{
V[block].erase(V[block].begin() + i);
break;
}
Build(block);
}
inline void Insert(int block, ll val)
{
int i = 0;
while (i < (int)V[block].size() && V[block][i] < val)
i ++;
V[block].insert(V[block].begin() + i, val);
Build(block);
}
inline void Refresh()
{
lzcnt = 0;
vector < int > srt(n, 0);
for (int i = 0; i < n; i ++)
srt[i] = i;
sort(srt.begin(), srt.end(), [&](int i, int j){return X[i] < X[j];});
for (int i = 0; i < nsq; i ++)
V[i].clear();
for (int i = 0; i < n; i ++)
V[i / SQ].push_back(X[srt[i]]), B[srt[i]] = i / SQ;
for (int i = 0; i < nsq; i ++)
Build(i);
}
inline int Calculate()
{
int Cnt = 0;
ll nw = -1e18;
for (int block = 0; block < nsq; block ++)
if (V[block].size() && V[block].back() > nw)
{
int lb = upper_bound(V[block].begin(), V[block].end(), nw) - V[block].begin();
assert(lb < (int)V[block].size());
Cnt += dp[block][lb].first;
nw = dp[block][lb].second;
}
return Cnt - EXTRAS;
}
void init(int _n, int _k, int _X[])
{
n = _n;
k = (ll)_k * SCALE + n;
for (int i = 0; i < n; i ++)
X[i] = _X[i] * (ll)SCALE + i;
ll val = (ll)(2e9 + 9);
while (n % SQ != 0)
X[n] = val * SCALE + n, n ++, val += (ll)(1e9 + 9), EXTRAS ++;
for (int i = 0; i < n; i ++)
V[i / SQ].push_back(X[i]), B[i] = i / SQ;
assert(n % SQ == 0);
nsq = n / SQ;
for (int i = 0; i < nsq; i ++)
Build(i);
}
int update(int i, int y)
{
lzcnt ++;
if (lzcnt + 3 >= SQ)
Refresh();
// If some stuff, refresh the data structure ...
ll val = y * (ll)SCALE + i;
// Removing the i-th element from it's block
{
int block = B[i];
Erase(block, X[i]);
}
// Adding the i-th element to it's new block
{
int block = 0;
for (; block < nsq; block ++)
if (block + 1 == nsq || V[block + 1][0] > val)
break;
if (block == nsq)
block --;
X[i] = val;
B[i] = block;
Insert(block, X[i]);
}
// Calculating the result :
return Calculate();
}
