#include "elephants.h"
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,sse4.1,popcnt,tune=native")
#include <bits/stdc++.h>
using namespace std;
const int maxn = 150670, C = 512;
int n, l, x[maxn], bl[maxn], to[maxn], sto[maxn], w[maxn];
#define INLINE inline __attribute__(( always_inline ))
struct costum_vec {
int a[2*C], sz = 0;
INLINE int& operator[] (int i) {
return a[i];
}
INLINE void push_back(int x) {
a[sz++] = x;
}
INLINE void pop_back() { --sz; }
INLINE void clear() {sz = 0;}
INLINE int size() { return sz; }
INLINE bool empty() { return !sz; }
INLINE int back() { return a[sz-1]; }
};
costum_vec b[maxn/C];
INLINE int lower_bound2(int X, int LBB = 0) {
int B = LBB, I = 0;
if(B > maxn/C || b[B].empty()) return n;
for(int z = 1<<11; z>>=1;) if(B+z < maxn/C && !b[B+z].empty() && x[b[B+z][0]] < X) B += z;
for(int z = 1<<10; z>>=1;) if(I+z < b[B].size() && x[b[B][I+z]] < X) I += z;
//cout << X << " // " << B << " " << I << '\n';
if(x[b[B][I]] < X && ++I == b[B].size()) I = 0, ++B;
//cout << X << " // " << B << " " << I << '\n';
//cout << "Final" << (b[B].empty() ? n : b[B][I]) << '\n';
return b[B].empty() ? n : b[B][I];
}
INLINE int lower_bound(int X, int &B) {
int I = 0;
while(B < maxn/C && !b[B].empty() && x[b[B].back()] < X) B++;
if(B >= maxn/C || b[B].empty()) return n;
for(int z = 1<<10; z>>=1;) if(I+z < b[B].size() && x[b[B][I+z]] < X) I += z;
//cout << X << " // " << B << " " << I << '\n';
if(x[b[B][I]] < X && ++I == b[B].size()) I = 0, ++B;
//cout << X << " // " << B << " " << I << '\n';
//cout << "Final" << (b[B].empty() ? n : b[B][I]) << '\n';
return b[B].empty() ? n : b[B][I];
}
INLINE void update(int i) {
//cout << "Updated block " << i << "\n";
int f = 0;
//for(auto v : b[i]) cout << v << " "; cout << '\n';
for(int p = 0; p < b[i].size(); p++) {
to[b[i][p]] = lower_bound(x[b[i][p]]+l+1, f);//, cout << v << " " << x[v]+l+1 << " " << to[v] << '\n';
}
for(int v, _v = b[i].size(); _v--;) {
v = b[i][_v];
if(bl[to[v]] == bl[v])
sto[v] = sto[to[v]], w[v] = 1+w[to[v]];
else sto[v] = v, w[v] = 1;
}
}
INLINE void pop(int v) {
for(int i = 0; i+1 < b[bl[v]].size(); i++)
if(b[bl[v]][i] == v) swap(b[bl[v]][i], b[bl[v]][i+1]);
b[bl[v]].pop_back();
update(bl[v]);
}
INLINE void push(int i) {
bl[i] = min((n-1)/C, bl[lower_bound2(x[i])]);
int bid = bl[i];
//for(auto &b : b[bid]) cout << x[b] << " "; cout << "F\n";
for(int p = 0; p < b[bid].size(); p++)
if(x[b[bid][p]] > x[i]) swap(b[bid][p], i);
b[bid].push_back(i);
//for(auto &b : b[bid]) cout << x[b] << " "; cout << "G\n";
update(bid);
}
INLINE void build() {
vector<int> ord;
ord.reserve(n);
for(int i = 0; i*C < n; i++)
for(int j = 0; j < b[i].size(); j++)
ord.push_back(b[i][j]);
if(ord.empty())
for(int i = 0; i < n; i++) ord.push_back(i);
for(int i = 0; i*C < n; i++) {
b[i].clear();
//b[i].reserve(2*C);
}
for(int i, pos = 0; pos < n; pos++) {
i = ord[pos];
bl[i] = pos/C;
b[bl[i]].push_back(i);
}
for(int i = 0; i*C < n; i++) update(i);
}
void init(int N, int L, int X[]) {
n = N;
l = L;
bl[n] = maxn;
for(int i = 0; i < n; i++) x[i] = X[i];
build();
}
INLINE int calc() {
int p = b[0][0], ans = 0, uwu = 0;
while(p != n) {
ans += w[p];
p = sto[p];
//cout << p << " " << sto[p] << '\n';
p = lower_bound(x[p]+l+1, uwu);
}
return ans;
}
int timer = 0;
int update(int i, int y) {
pop(i);
//for(int uwu = 0; uwu < 2; uwu++, cout << " | ")
// for(auto i : b[uwu]) cout << x[i] << " ";cout << ":\n";
//cout << "x_" << i << " := " << y << endl;
x[i] = y;
push(i);
//for(int uwu = 0; uwu < 2; uwu++, cout << " | ")
// for(auto i : b[uwu]) cout << x[i] << " ";cout << ":\n";
if(++timer == 1.5*C-1) timer = 0, build();
return calc();
}
