#include "elephants.h"
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
typedef struct ele{
int bc;
int end;
int bf;
int pos;
int id;
} ele;
ele bucket[1000][1000];
int sz[1000];
int anzB;
int n;
int l;
int sele[200000];
int bele[200000];
int ih[200000];
void calcB(int idx){
int s = sz[idx];
int tmp = s-1;
for(int i = s-1;i>=0;i--){
if(bucket[idx][i].bf == -1 && (i == s-1 || bucket[idx][i+1].bf == -1)){
bucket[idx][i].end = bucket[idx][i].pos + l;
bucket[idx][i].bc = 1;
}else{
int b = bucket[idx][i].bf;
if(b == -1){
b = bucket[idx][i+1].bf;
bucket[idx][i].bf = b;
};
bucket[idx][i].end = bucket[idx][b].end;
bucket[idx][i].bc = bucket[idx][b].bc + 1;
};
while(tmp != -1 && bucket[idx][tmp].pos +l >= bucket[idx][i].pos){
tmp--;
};
if(tmp != -1){
bucket[idx][tmp].bf = i;
};
};
};
void delE(int idx, int id){
int s = sz[idx]-1;
int tmp = bucket[idx][s].pos;
int itmp = bucket[idx][s].id;
while(s != 0 && itmp != id){
std::swap(tmp,bucket[idx][s-1].pos);
std::swap(itmp,bucket[idx][s-1].id);
s--;
};
sz[idx]--;
for(int i = 0;i<sz[idx];i++){
bucket[idx][i].bf = -1;
};
calcB(idx);
};
void insertE(int idx, int id, int pos){
bele[id] = idx;
int s = sz[idx]-1;
int tmp = s > -1 ?bucket[idx][s].pos:0;
int itmp = s > -1 ?bucket[idx][s].id:0;
while(s != -1 && tmp > pos){
std::swap(tmp,bucket[idx][s+1].pos);
std::swap(itmp,bucket[idx][s+1].id);
s--;
tmp = s > -1 ?bucket[idx][s].pos:0;
itmp = s > -1 ?bucket[idx][s].id:0;
// printf("%d %d %d\n",tmp,pos,s);
};
bucket[idx][s+1].pos = pos;
bucket[idx][s+1].id = id;
sz[idx]++;
for(int i = 0;i<sz[idx];i++){
bucket[idx][i].bf = -1;
};
calcB(idx);
};
int findN(int idx, int &aktP){
int idxR = sz[idx]-1;
int idxL = 0;
if(bucket[idx][idxR].pos <= aktP){
//printf("%d %d %d\n",idx,idxR,bucket[idx][idxR].pos);
return 0;
}else{
while(idxR > idxL){
int idxM = (idxR + idxL)/2;
if(bucket[idx][idxM].pos <= aktP){
idxL = idxM+1;
}else{
idxR = idxM;
};
};
aktP = bucket[idx][idxL].end;
return bucket[idx][idxL].bc;
};
};
int querry(){
int aktP = 0;
int aktC = 0;
int first = 0;
for(int i = 0;i<anzB;i++){
if(sz[i]){
if(!first){
aktC += bucket[i][0].bc;
aktP += bucket[i][0].end;
first = 1;
//printf("%d %d\n",aktC,aktP);
}else{
//printf("%d %d geil\n",sz[i],anzB);
aktC += findN(i,aktP);
//printf("%d %d\n",aktC,aktP);
};
};
};
return aktC;
};
void makeB(){
anzB = std::ceil(std::sqrt(n));
int cnt = 0;
int cnt1 = 0;
for(int i = 0;i<anzB;i++){
sz[i] = 0;
};
for(int i = 0;i<n;i++){
bucket[cnt][cnt1].pos = sele[i];
bucket[cnt][cnt1].bf = -1;
bucket[cnt][cnt1++].id = ih[i];
bele[ih[i]] = cnt;
if(cnt1 == anzB){
sz[cnt] = cnt1;
calcB(cnt);
cnt1 = 0;
cnt++;
};
};
if(cnt1){
sz[cnt] = cnt1;
calcB(cnt);
};
};
void makeN(){
int cnt = 0;
for(int i = 0;i<anzB;i++){
for(int j = 0;j<sz[i];j++){
ih[cnt] = bucket[i][j].id;
sele[cnt] = bucket[i][j].pos;
cnt++;
};
};
makeB();
};
void printB(){
for(int i = 0;i<anzB;i++){
if(sz[i] == 0){
printf("Empty");
};
for(int j = 0;j<sz[i];j++){
printf("(%d, %d, %d, %d, %d) ",bucket[i][j].pos,bucket[i][j].id,bucket[i][j].bc,bucket[i][j].end,bucket[i][j].bf);
puts("");
};
puts("");
};
puts("");
puts("");
};
void init(int N, int L, int X[])
{
n = N;
l = L;
for(int i = 0;i<n;i++){
sele[i] = X[i];
ih[i] = i;
};
makeB();
//printB();
}
int up = 0;
int update(int i, int y)
{
int idx = bele[i];
delE(idx,i);
//printf("Delete\n");
//printB();
int ins = 0;
for(int j = 0;j<anzB&&!ins;j++){
if(sz[j]){
if(bucket[j][sz[j]-1].pos >= y){
if(bucket[j][0].pos >= y && j != 0){
insertE(j-1,i,y);
}else{
insertE(j,i,y);
};
ins = 1;
};
};
};
if(!ins){
insertE(anzB-1,i,y);
};
//printf("querry\n");
//printB();
int erg = querry();
if(up == anzB){
makeN();
//printf("new\n");
//printB();
up = 0;
}else{
up++;
};
return erg;
}
