#include <bits/stdc++.h>
#define K 500
using namespace std;
//#include "elephants.h"
int n, l, x[150005];
int tmp[150005];
struct BUCKET{
int a[150005], ct[150005], r[150005], sz;
void comp(){
int k = sz-1;
for (int i = sz-1; i >= 0; i--){
while (k > i && a[k-1] - a[i] > l) k--;
if (a[sz-1] - a[i] <= l){
ct[i] = 1; r[i] = a[i]+l;
}
else ct[i] = ct[k]+1, r[i] = r[k];
//printf("%d -> %d: ct = %d, r = %d\n",a[i],a[k],ct[i],r[i]);
}
}
} bk[305];
void init(int N, int L, int X[])
{
n = N;
l = L;
for (int i = 0; i < n; i++) x[i] = X[i];
for (int i = 0; i <= n/K; i++){
bk[i].sz = 0;
for (int j = i*K; j < min((i+1)*K,n); j++){
bk[i].a[j%K] = x[j];
bk[i].sz++;
}
bk[i].comp();
}
}
void rebuild_all(){
//printf("REBUILD ALL");
int N = 0;
for (int i = 0; i <= n/K; i++){
for (int j = 0; j < bk[i].sz; j++){
tmp[N++] = bk[i].a[j];
}
}
for (int i = 0; i <= n/K; i++){
bk[i].sz = 0;
for (int j = i*K; j < min((i+1)*K,n); j++){
bk[i].a[j%K] = tmp[j];
bk[i].sz++;
}
bk[i].comp();
}
}
void add(int x){
//printf("adding %d\n",x);
for (int i = 0; i <= n/K; i++){
if (i == (n-1)/K || (bk[i].sz && ((bk[i].a[0] > x) || (bk[i].a[0] <= x && x < bk[i+1].a[0])) )){
//printf("adding to bucket %d\n",i);
if (bk[i].sz == 0 || bk[i].a[0] > x){
//printf("position %d\n",0);
for (int k = bk[i].sz-1; k >= 0; k--){
bk[i].a[k+1] = bk[i].a[k];
}
bk[i].a[0] = x;
}
else{
for (int j = 0; j < bk[i].sz; j++){
if ((bk[i].a[j] <= x && x < bk[i].a[j+1]) || j+1 == bk[i].sz){
//printf("position %d\n",j+1);
for (int k = bk[i].sz-1; k >= j+1; k--){
bk[i].a[k+1] = bk[i].a[k];
}
bk[i].a[j+1] = x;
break;
}
}
}
bk[i].sz++;
bk[i].comp();
break;
}
}
}
void del(int x){
// printf("deleting %d\n",x);
for (int i = 0; i <= n/K; i++){
if (bk[i].sz == 0) continue;
if (bk[i].a[0] <= x && x <= bk[i].a[bk[i].sz-1]){
//printf("deleting from bucket %d\n",i);
for (int j = 0; j < bk[i].sz; j++){
if (bk[i].a[j] == x){
//printf("position %d\n",j);
for (int k = j; k < bk[i].sz; k++){
bk[i].a[k] = bk[i].a[k+1];
}
break;
}
}
bk[i].a[bk[i].sz] = 0;
bk[i].sz--;
bk[i].comp();
break;
}
}
}
int hmmmmm;
int solve(){
//printf("solving\n");
int curpos = -1;
int ans = 0;
for (int i = 0; i <= n/K; i++){
if (bk[i].sz == 0 || curpos >= bk[i].a[bk[i].sz-1]) continue;
//printf("%d ",curpos);
int nx = upper_bound(bk[i].a, bk[i].a+bk[i].sz,curpos) - bk[i].a;
//printf("-> nx = %d (%d), ",nx,bk[i].a[nx]);
//printf("add %d to %d\n",bk[i].ct[nx],ans);
ans += bk[i].ct[nx];
curpos = bk[i].r[nx];
}
return ans;
}
void debug(){
int last = -1;
int cur = 0;
for (int i = 0; i <= n/K; i++){
//printf("bucket %d: ",i);
for (int j = 0; j < bk[i].sz; j++){
//printf("%d ",bk[i].a[j]);
assert(bk[i].a[j] >= last);
last= bk[i].a[j];
}
// printf("\n");
}
}
int numQ = 0;
int update(int i, int y)
{
hmmmmm++;
//printf("up %d\n",hmmmmm);
//printf("update %d %d->%d\n",i,x[i],y);
if (++numQ == K){
rebuild_all();
numQ = 0;
}
del(x[i]);
x[i] = y;
add(x[i]);
//debug();
return solve();
}
