#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int maxBlockLen = 500;
int n, length;
int numBlock;
int block[400][1000], blockSz[1000];
int bFind(int id,int val){
for(int i=0;;i++)
if (block[id][i] == val) return i;
}
void bInsert(int id,int pos,int val){
for(int i=blockSz[id];i>pos;i--)
block[id][i] = block[id][i-1];
block[id][pos] = val;
blockSz[id] ++;
}
void bErase(int id,int pos){
blockSz[id] --;
for(int i=pos;i<blockSz[id];i++)
block[id][i] = block[id][i+1];
}
ii startFromThis[400][1000]; // [blockId][position] = {last position, how many jumps}
int elephantPos[150005], elephantBLock[150005];
void reBuild(int blockId){
//~ sort(block[blockId].begin(), block[blockId].end());
// assuming sorted
int nextPos = blockSz[blockId];
for(int i = blockSz[blockId]-1;i >= 0; i--){
while(nextPos > 0 && block[blockId][nextPos-1] > block[blockId][i] + length)
-- nextPos;
if (nextPos == blockSz[blockId])
startFromThis[blockId][i] = {block[blockId][i], 0};
else
startFromThis[blockId][i] = startFromThis[blockId][nextPos],
startFromThis[blockId][i].second ++;
}
}
int lst[150005];
void reBuildFull(){
for(int i=1;i<=numBlock;i++) blockSz[i] = 0;
numBlock = 1;
for(int i=0;i<n;i++) lst[i] = i;
sort(lst, lst+n, [&](int x,int y){
return elephantPos[x] < elephantPos[y];
});
for(int i=0;i<n;i++){
if (blockSz[numBlock] == maxBlockLen)
++ numBlock;
block[numBlock][blockSz[numBlock]++] = elephantPos[lst[i]];
elephantBLock[lst[i]] = numBlock;
}
for(int i=1;i<=numBlock;i++){
reBuild(i);
}
}
int cntUpdTimes;
int update(int elephantId, int newPos){
if (++cntUpdTimes % 450 == 0)
reBuildFull();
//~ cout << "turn " << cntUpdTimes << endl;
bErase(elephantBLock[elephantId],
bFind(elephantBLock[elephantId], elephantPos[elephantId]));
reBuild(elephantBLock[elephantId]);
elephantPos[elephantId] = newPos;
for(int i=1;i<=numBlock;i++){
if (i == numBlock || newPos <= block[i][blockSz[i]-1]){
// block[i].empty() only occur when i = numBlock
elephantBLock[elephantId] = i;
for(int j=0;j<=blockSz[i];j++){
if (j == blockSz[i] || newPos <= block[i][j]){
bInsert(i, j, newPos);
break;
}
}
reBuild(i);
break;
}
}
// find res
int res = 0;
int last = (int)-(1e9+5);
for(int i=1;i<=numBlock;i++){
int startHere = upper_bound(block[i], block[i]+blockSz[i], last + length) - block[i];
if (startHere == blockSz[i]) continue;
res += startFromThis[i][startHere].second + 1;
last = startFromThis[i][startHere].first;
}
return res;
}
void init(int N, int L, int X[]){
n = N;
length = L;
for(int i=0;i<N;i++){
elephantPos[i] = X[i];
}
reBuildFull();
}
