#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#include "elephants.h"
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
const int MAXN = 70000;
int X[MAXN], n, L;
int A[MAXN]; // TODO: multiset
void init(int N, int L_, int X_[]) {
L = L_;
for (int i = 0; i < N; i++) {
X[i] = X_[i];
A[i] = X[i];
}
n = N;
}
int update(int i, int y) {
int ind = lower_bound(A, A + n, X[i]) - A;
X[i] = y;
A[ind] = y;
while (ind > 0 && A[ind] < A[ind - 1]) {
swap(A[ind], A[ind - 1]);
ind--;
}
while (ind < n - 1 && A[ind] > A[ind + 1]) {
swap(A[ind], A[ind + 1]);
ind++;
}
int ans = 0;
int v = -(L + 1);
for (int i = 0; i < MAXN; i++) {
if (A[i] > v + L) {
v = A[i];
ans++;
}
}
return ans;
}
