#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int kN = 1e5 + 5e4;
const int bucketSize = 1e3;
const int kBuckets = 150;
int n, len, a[kN], bucket[kN], indexInBucket[kN];
int updates, auxSize, auxIndices[kN];
class bucket_t {
private:
int N, indices[2 * bucketSize];
int req[2 * bucketSize], maxReach[2 * bucketSize];
public:
void reset() {
N = 0;
}
bool isEmpty() {
return N == 0;
}
int getSize() {
return N;
}
int last() {
return a[indices[N - 1]];
}
void add(int index) {
indices[N++] = index;
}
void addAll() {
for (int i = 0; i < N; ++i) {
auxIndices[auxSize++] = indices[i];
}
}
int jumps(int index) {
return req[index];
}
int furthest(int index) {
return maxReach[index];
}
void build() {
int r = N - 1;
for (int l = N - 1; l >= 0; --l) {
while (a[indices[r]] - a[indices[l]] > len) {
r -= 1;
}
if (r == N - 1) {
req[l] = 1;
maxReach[l] = a[indices[l]] + len;
} else {
req[l] = req[r + 1] + 1;
maxReach[l] = maxReach[r + 1];
}
}
}
void rem(int pos) {
for (int i = pos; i < N - 1; ++i) {
indices[i] = indices[i + 1];
indexInBucket[indices[i]] = i;
}
N -= 1;
build();
}
void ins(int index) {
int ptr = N - 1;
while (ptr >= 0 && a[index] < a[indices[ptr]]) {
ptr -= 1;
}
for (int i = N; i > ptr + 1; --i) {
indices[i] = indices[i - 1];
indexInBucket[indices[i]] = i;
}
indices[ptr + 1] = index;
indexInBucket[index] = ptr + 1;
N += 1;
build();
}
int upperBound(int x) {
int l = -1, r = N;
while (r - l > 1) {
int mid = (l + r) / 2;
if (mid != -1 && (mid == N || x < a[indices[mid]])) {
r = mid;
} else {
l = mid;
}
}
return r;
}
} buckets[kBuckets];
void init(int N, int L, int X[]) {
n = N;
len = L;
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
buckets[i].reset();
}
for (int i = 0; i < n; ++i) {
a[i] = X[i];
bucket[i] = i / bucketSize;
indexInBucket[i] = i % bucketSize;
buckets[i / bucketSize].add(i);
}
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
buckets[i].build();
}
}
void rebuild() {
auxSize = 0;
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
buckets[i].addAll();
buckets[i].reset();
}
for (int i = 0; i < n; ++i) {
bucket[auxIndices[i]] = i / bucketSize;
indexInBucket[auxIndices[i]] = i % bucketSize;
buckets[i / bucketSize].add(auxIndices[i]);
}
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
buckets[i].build();
}
}
int query() {
int res = 0;
int reach = -1;
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
if (!buckets[i].isEmpty() && reach < buckets[i].last()) {
int index = buckets[i].upperBound(reach);
res += buckets[i].jumps(index);
reach = buckets[i].furthest(index);
}
}
return res;
}
int update(int index, int x) {
buckets[bucket[index]].rem(indexInBucket[index]);
a[index] = x;
bucket[index] = -1;
for (int i = 0; i <= (n - 1) / bucketSize && bucket[index] == -1; ++i) {
if (!buckets[i].isEmpty() && x <= buckets[i].last()) {
bucket[index] = i;
}
}
if (bucket[index] == -1) {
bucket[index] = (n - 1) / bucketSize;
}
buckets[bucket[index]].ins(index);
updates += 1;
if (updates == bucketSize) {
rebuild();
updates = 0;
}
return query();
}
