#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
const int N = 150000 + 5;
const int K = 1500;
const int T = N / K + 5;
int n, l;
int a[N], gr[N], nxt[N], need[N];
vector < ii > v[T];
void rebuild(int i) {
int last = 0;
if(v[i].size())
last = v[i].back().first;
int pos = (int) v[i].size() - 1;
for(int j = (int) v[i].size() - 1; j >= 0; j--) {
int x = v[i][j].first;
int id = v[i][j].second;
gr[id] = i;
if(x + l >= last) {
nxt[id] = id;
need[id] = 0;
}
else {
while(pos > j + 1 and x + l < v[i][pos - 1].first)
pos--;
nxt[id] = nxt[v[i][pos].second];
need[id] = need[v[i][pos].second] + 1;
}
}
}
ii b[N];
void init(bool flag = 0) {
if(flag) {
for(int i = 0; i < n; i++)
b[i] = ii(a[i], i);
}
else {
int sz = 0;
for(int i = 0; i * K < n; i++) {
for(int j = 0; j < v[i].size(); j++)
b[sz++] = v[i][j];
}
}
int ind = 0;
for(int i = 0; i * K < n; i++) {
v[i].clear();
for(int j = i * K; j < n and j < (i + 1) * K; j++) {
v[i].push_back(b[j]);
}
ind = i;
}
for(int i = ind; i >= 0; i--)
rebuild(i);
}
void init(int N, int L, int X[]) {
n = N;
l = L;
for(int i = 0; i < n; i++) {
a[i] = X[i];
}
a[n] = 2 * inf;
init(1);
}
int upCnt = 0;
int update(int i, int x) {
int ind = gr[i];
v[ind].erase(lower_bound(v[ind].begin(), v[ind].end(), ii(a[i], i)));
rebuild(ind);
a[i] = x;
for(int j = 0; j * K < n; j++) {
ind = j;
if(v[j].size() and ii(a[i], i) <= v[j].back())
break;
}
v[ind].insert(lower_bound(v[ind].begin(), v[ind].end(), ii(a[i], i)), ii(a[i], i));
rebuild(ind);
upCnt++;
if(upCnt == 1500) {
upCnt = 0;
init();
}
int pos = v[0].front().second, ans = 0;
while(pos < n) {
if(nxt[pos] == pos) {
ans++;
int ind = gr[pos] + 1;
while(ind * K < n and a[pos] + l >= v[ind].back().first)
ind++;
if(ind * K >= n)
break;
pos = lower_bound(v[ind].begin(), v[ind].end(), ii(a[pos] + l + 1, 0)) -> second;
}
else {
ans += need[pos];
pos = nxt[pos];
}
}
return ans;
}
