#include "elephants.h"
#include <algorithm>
using namespace std;
const int maxGroup = 300;
const int maxSize = 500;
int gcnt,wgroup[maxGroup*maxSize];
int size[maxGroup],start[maxGroup],index[maxGroup][maxSize*2],pos[maxGroup][maxSize*2],cnt[maxGroup][maxSize*2],npos[maxGroup][maxSize*2];
int l;
void makejump(int g)
{
int s = size[g], *p = pos[g], *c = cnt[g], *n = npos[g];
n[s] = -1; c[s] = 0;
for (int i=s-1,j=s-1;i>=0;i--){
while (p[i] + l < p[j]) j--; j++;
n[i] = (n[j] == -1) ? p[i] + l : n[j];
c[i] = c[j] + 1; j--;
}
}
void init(int N, int L, int X[])
{
l = L;
for (int i=0;i<N;i++){
int gp = i / maxSize;
wgroup[i] = gp;
index[gp][size[gp]] = i;
pos[gp][size[gp]++] = X[i];
gcnt = gp + 1;
}
for (int g=0;g<gcnt;g++){
start[g] = pos[g][0];
makejump(g);
}
}
int indtemp[maxGroup*maxSize],postemp[maxGroup*maxSize];
void justify()
{
int c = 0;
for (int i=0;i<gcnt;i++){
int *ind = index[i], *p = pos[i];
for (int j=0;j<size[i];j++){
indtemp[c] = ind[j];
postemp[c] = p[j];
c++;
}
size[i] = 0;
}
for (int i=0;i<c;i++){
int gp = i / maxSize;
wgroup[indtemp[i]] = gp;
index[gp][size[gp]] = indtemp[i];
pos[gp][size[gp]++] = postemp[i];
gcnt = gp + 1;
}
for (int g=0;g<gcnt;g++){
start[g] = pos[g][0];
makejump(g);
}
}
int update(int ind, int y)
{
int g = wgroup[ind];
for (int i=0;i<size[g];i++) if (index[g][i] == ind){
for (int j=i+1;j<size[g];j++){
index[g][j-1] = index[g][j];
pos[g][j-1] = pos[g][j];
}
start[g] = pos[g][0];
size[g]--;
break;
}
if (size[g] == 0) justify();
else makejump(g);
g = lower_bound(start,start+gcnt,y) - start - 1;
if (g < 0) g++;
int i = lower_bound(pos[g],pos[g]+size[g],y) - pos[g];
for (int j=size[g];j>i;j--){
index[g][j] = index[g][j-1];
pos[g][j] = pos[g][j-1];
}
wgroup[ind] = g;
index[g][i] = ind;
pos[g][i] = y;
start[g] = pos[g][0];
size[g]++;
if (size[g] == maxSize * 2) justify();
else makejump(g);
int last = -1, k = 0;
for (int i=0;i<gcnt;i++){
if (pos[i][size[i]-1] <= last) continue;
int u = upper_bound(pos[i],pos[i]+size[i],last) - pos[i];
last = npos[i][u];
k += cnt[i][u];
}
return k;
}
