#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define MAXE 150051
#define BLOCK 400
int n, bn, l, ele[MAXE], tmp[MAXE], cooltime;
int p[BLOCK][BLOCK*2], sz[BLOCK][BLOCK*2], la[BLOCK][BLOCK*2], pn[BLOCK], pl[BLOCK];
void calc(int b){
for(int i=pn[b]-1; i>=0; i--){
int nxt = lower_bound( p[b]+i+1, p[b]+pn[b], p[b][i] + l + 1 ) - p[b];
if( nxt == pn[b] ) sz[b][i] = 1, la[b][i] = p[b][i] + l + 1;
else sz[b][i] = sz[b][nxt] + 1, la[b][i] = la[b][nxt];
}
}
void mkblock( int X[] ){
for(int i=0; i<bn; i++) pn[i] = 0;
for(int i=0; i<n; i++){
int b = i / BLOCK;
int& bs = pn[b];
p[b][bs++] = X[i];
} bn = ( n-1 ) / BLOCK + 1;
for(int i=0; i<bn; i++)
calc(i), pl[i] = p[i][pn[i]-1];
}
void init(int N, int L, int X[]){
n = N; l = L;
for(int i=0;i<n;i++) ele[i] = X[i];
mkblock( X );
}
int update(int i, int y)
{
if( ++cooltime == BLOCK ){
cooltime = 0;
bool xd = false, ya = false; int tn = 0, x;
x = ele[i]; ele[i] = y;
for(int i=0; i<bn; i++)
for(int j=0; j<pn[i]; j++){
if( !xd && p[i][j] == x ) { xd = true; continue; }
if( !ya && p[i][j] > y ) { ya = true; tmp[tn++] = y; }
tmp[tn++] = p[i][j];
}
if(!ya) tmp[tn++] = y;
mkblock( tmp );
}else{
int xb = lower_bound( pl, pl + bn, ele[i] ) - pl;
int xp = lower_bound( p[xb], p[xb] + pn[xb], ele[i] ) - p[xb];
pn[xb]--; for(int i=xp; i<pn[xb]; i++) p[xb][i] = p[xb][i+1];
calc(xb); if(pn[xb]!=0) pl[xb] = p[xb][pn[xb]-1];
ele[i] = y;
int yb = lower_bound( pl, pl + bn, ele[i] ) - pl; if(yb == bn) yb--;
int yp = lower_bound( p[yb], p[yb] + pn[yb], ele[i] ) - p[yb];
for(int i=pn[yb]; i>yp; i--) p[yb][i] = p[yb][i-1]; pn[yb]++; p[yb][yp] = ele[i];
calc(yb); pl[yb] = p[yb][pn[yb]-1];
}
int ret = 0, pos = -1;
for(int i=0; i<bn; i++){
int j = lower_bound( p[i], p[i] + pn[i], pos ) - p[i];
if( j == pn[i] ) continue;
ret += sz[i][j]; pos = la[i][j];
}
return ret;
}
