#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
inline void read() {}
template <class S>
inline void read(S &arg) {
cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
while (Lptr != Rptr) {
read(*Lptr);
Lptr++;
}
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
read(arg);
read(rest...);
}
inline void write() {}
template <class S>
inline void write(S arg) {
cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char C_ = ' ') {
if (Lptr != Rptr) {
write(*Lptr);
Lptr++;
}
while (Lptr != Rptr) {
write(C_);
write(*Lptr);
Lptr++;
}
}
template <class S, class... T>
inline void write(S arg, T... rest) {
write(arg);
write(' ');
write(rest...);
}
#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
template <class T, class S>
inline bool smin(T &a, S b) {
return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
return a < (T)b ? a = b, 1 : 0;
}
constexpr int MOD = 1e9 + 7;
constexpr int N = 150 * 1000 + 10;
template <typename T>
inline T mod(T &v) {
return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
return mod(l += r);
}
ll po(ll v, ll u) {
return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}
const int sq = 600;
int n, L, pos[N];
vector<pii> s[N / sq + 10];
vector<pii> dp[N / sq + 10];
void relax(int id) {
int e = s[id].size() - 1;
while (e > 0 && s[id][e] < s[id][e - 1]) {
swap(s[id][e], s[id][e - 1]);
e--;
}
dp[id] = vector<pii>(s[id].size());
int z = s[id].size();
for (int i = s[id].size() - 1; ~i; i--) {
while (s[id][z - 1].first > s[id][i].first + L) z--;
dp[id][i].first = 1;
dp[id][i].second = s[id][i].first + L;
if (z != s[id].size()) {
dp[id][i].first += dp[id][z].first;
dp[id][i].second = dp[id][z].second;
}
}
}
void init(int n_, int L_, int X[]) {
n = n_;
L = L_;
memcpy(pos, X, 4 * n_);
vector<pii> vec;
rep(i, 0, n) vec.pb({X[i], i});
sort(all(vec));
for (int i = 0; i * sq < n; i++) {
int l = i * sq;
int r = min(n, l + sq);
s[i].clear();
rep(j, l, r) s[i].pb(vec[j]);
relax(i);
}
}
int Nu;
int update(int me, int y) {
if (n == 1) return 1;
Nu++;
if (Nu % sq == 0) init(n, L, pos);
bool flag = false;
for (int i = 0; !flag; i++)
if (s[i].size() && pii(pos[me], me) <= s[i].back()) {
for (int j = 0; !flag; j++)
if (s[i][j] == pii(pos[me], me)) {
s[i].erase(s[i].begin() + j);
flag = true;
}
relax(i);
}
pos[me] = y;
for (int i = 0;; i++)
if ((i + 1) * sq >= n || (s[i].size() && pii(pos[me], me) <= s[i].back())) {
s[i].pb(pii(pos[me], me));
relax(i);
break;
}
int res = 0;
int last = -1;
for (int i = 0; i * sq < n; i++) {
if (s[i].empty() || s[i].back().first <= last) continue;
int id = lower_bound(all(s[i]), pii(last + 1, -1)) - s[i].begin();
res += dp[i][id].first;
last = dp[i][id].second;
}
return res;
}
