#include "elephants.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
int len, A[160001], n, a[160001];
const int BlockSize = 500, BigSize = BlockSize*2;
int Counter, blen;
struct Block{
int arr[BigSize], where[BigSize], pos[BigSize], need[BigSize], sz;
int max(){return arr[sz-1];}
int min(){return arr[0];}
bool contain(int x){return x >= min() && x <= max();}
void clear(){sz=0;}
void recalc(){
for(int i=sz-1, j=sz-1;i>=0;i--){
int r = arr[i] + len;
while(j>0 && arr[j-1] > r)j--;
if(r >= max()){
need[i] = 1;
pos[i] = r;
}else {
need[i] = need[j]+1;
pos[i] = pos[j];
}
}
}
void insert(int x){
arr[sz++] = x;
int p = sz - 1;
while(p && arr[p]<arr[p-1])swap(arr[p], arr[p-1]), --p;
recalc();
}
void remove(int x){
int p = 0;
while(arr[p] < x) ++p;
while(p+1 < sz)arr[p] = arr[p+1],p++;
recalc();
}
void rebuild(int l, int r){
sz = r-l;
for(int i=0;i<sz;i++){
arr[i] = a[l+i];
}
}void advance(int &r, int &cnt) {
int p = upper_bound(arr,arr+sz, r)-arr;
r = pos[p], cnt += need[p];
}
}block[160000/BlockSize];
void Remove(int x){
for(int i=0;i<blen;++i){
if (block[i].contain(x)){
block[i].remove(x);
return;
}
}
}
void Insert(int x){
for(int i=0;i<blen;i++){
if (i==blen-1 || block[i+1].min()>x){
block[i].insert(x);
return;
}
}
}
int query(){
int cur=-1, ans=0;
for(int i=0;i<blen;i++){
if (cur >= block[i].max())continue;
block[i].advance(cur,ans);
}
return ans;
}
void init(int N, int L, int X[]){
len = L;
n = N;
for(int i=0;i<N;i++)A[i] = a[i] = X[i];
sort(a, a+n);
for(int id=0;;id++){
int L = id*BlockSize, R = min(n, L+BlockSize);
block[id].rebuild(L, R);
blen = id+1;
if(R == n)break;
}
}
int update(int i, int y){
Counter++;
if(Counter == BlockSize){
A[i] = y;
Counter = 0;
init(n,len,A);
return query();
}
Remove(A[i]);
A[i] = y;
Insert(A[i]);
return query();
}
