#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
const int MXN = 15e4+5, sq = 600, sqi = MXN/sq+5;
int n, L, X[MXN], szx[sqi], arr[sqi][sq<<1], xs[MXN], num, dp[sqi][sq<<1], wh[sqi][sq<<1];
pii lim[sqi];
inline pii gx(int i) { return pii(X[i], i); }
inline void rebuild(int t) {
int r=szx[t]-1;
for(int l=szx[t]-1; l>=0; l--) {
while(X[arr[t][l]]+L<X[arr[t][r]]) r--;
if(r+1<szx[t]) {
dp[t][l] = dp[t][r+1] + 1;
wh[t][l] = wh[t][r+1];
}
else {
dp[t][l] = 1;
wh[t][l] = X[arr[t][l]]+L+1;
}
}
}
inline void build(bool fix_xs=1) {
if(fix_xs) {
int ptr=0;
for(int t=0; t<num; t++) {
for(int i=0; i<szx[t]; i++)
xs[ptr++] = arr[t][i];
szx[t] = 0;
}
num = 0;
}
for(int i=0; i<n; i+=sq) {
for(int j=i; j<i+sq && j<n; j++)
arr[num][szx[num]++] = xs[j],
lim[num] = {X[xs[j]], xs[j]};
rebuild(num++);
}
lim[num-1] = {1e9, 1e9};
}
inline void erase(int i) {
for(int t=0; t<num; t++)
if(gx(i)<=lim[t]) {
for(int j=0; j<szx[t]; j++)
if(arr[t][j]==i) {
for(int k=j+1; k<szx[t]; k++)
arr[t][k-1] = arr[t][k];
szx[t]--;
break;
}
rebuild(t);
break;
}
}
inline void insert(int i) {
for(int t=0; t<num; t++)
if(gx(i)<=lim[t]) {
arr[t][szx[t]++] = i;
for(int j=szx[t]-1; j>0 && gx(arr[t][j])<gx(arr[t][j-1]); j--)
swap(arr[t][j], arr[t][j-1]);
rebuild(t);
break;
}
}
void init(int N, int L, int X[]) {
n = N;
::L = L;
for(int i=0; i<n; i++) ::X[i] = X[i], xs[i] = i;
build(0);
}
int cnt;
int update(int i, int y) {
erase(i);
X[i] = y;
insert(i);
if((++cnt)==sq) {
build();
cnt = 0;
}
int cur=0, ans=0;
for(int t=0, l, r, mid; t<num; t++) {
l=-1, r=szx[t], mid;
while(r-l>1) {
mid = l+r>>1;
(X[arr[t][mid]]>=cur ? r : l) = mid;
}
if(r<szx[t]) {
ans += dp[t][r];
cur = wh[t][r];
}
}
return ans;
}
