#include "elephants.h"
#define MAXN 500002
int n, l;
int elephants[MAXN];
int positions[MAXN];
void init(int N, int L, int X[])
{
l = L;
n = N;
for (int i=0; i < n; i++) {
elephants[i] = X[i];
positions[i] = X[i];
}
}
int update(int i, int y)
{
int result = 0;
int last_covered = -1;
int current_pos = elephants[i];
elephants[i] = y;
bool type = y < current_pos;
int carrying = -1;
bool eating = false;
for (int i = 0; i < n; i++) {
if (type) {
if (positions[i] > y ) {
carrying = positions[i];
positions[i] = y;
y = 2000000000;
if (carrying == current_pos) {
carrying = -1;
}
} else if (carrying != -1) {
if (positions[i] == current_pos) {
positions[i] = carrying;
carrying = -1;
} else {
carrying ^= positions[i];
positions[i] ^= carrying;
carrying ^= positions[i];
}
}
}
else {
if (eating) {
if (positions[i+1] >= y || i == n-1) {
positions[i] = y;
eating = false;
} else {
positions[i] = positions[i+1];
}
} else if (positions[i] == current_pos) {
current_pos = -1;
eating = true;
i--;
continue;
}
}
if (last_covered < positions[i]) {
result++;
last_covered = positions[i] + l;
}
}
return result;
}
