#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
static const int nmax = 15e4;
static const int rad = 400 * 4;
static int n, L;
static int up_cnt;
static int bucket[nmax + 1];
static pair<int, int> pozitii[nmax + 1];
static int nrb;
static int sz[nmax / rad + 1];
struct str {
int x, ind, pos, dp;
};
str v[nmax / rad + 1][2 * rad + 5];
void compute (int b) {
int ind = sz[b];
for (int i = sz[b] - 1; i >= 0; -- i) {
while (ind - 1 > i && v[b][ind - 1].x > v[b][i].x + L) {
-- ind;
}
if (ind == sz[b]) {
v[b][i].dp = 1;
v[b][i].pos = v[b][i].x + L;
} else {
v[b][i].dp = v[b][ind].dp + 1;
v[b][i].pos = v[b][ind].pos;
}
}
}
void refa_bucketuri () {
int idx = 0;
for (int b = 0; b < nrb; ++ b) {
for (int k = 0; k < sz[b]; ++ k) {
pozitii[idx ++] = {v[b][k].x, v[b][k].ind};
}
sz[b] = 0;
}
for (int i = 0, b = 0; i < n; i += rad, ++ b) {
for (int j = i; j < i + rad && j < n; ++ j) {
v[b][sz[b]].x = pozitii[j].first;
v[b][sz[b] ++].ind = pozitii[j].second;
bucket[pozitii[j].second] = b;
}
compute(b);
}
}
void init (int N, int l, int X[]) {
n = N;
L = l;
for (int i = 0; i < n; i += rad, ++ nrb) {
for (int j = i; j < i + rad && j < n; ++ j) {
v[nrb][sz[nrb]].x = X[j];
v[nrb][sz[nrb] ++].ind = j;
}
}
refa_bucketuri();
}
int solve () {
int total = 0;
int posst = -1;
int n2 = 1;
for (n2 = 1; (n2 << 1) <= 3 * rad; n2 <<= 1) {
}
for (int i = 0; i < nrb; ++ i) {
if (sz[i] == 0) continue;
if (v[i][sz[i] - 1].x <= posst)
continue;
int pos = -1;
for (int step = n2; step > 0; step >>= 1) {
if (pos + step < sz[i] && v[i][pos + step].x <= posst)
pos += step;
}
++ pos;
total += v[i][pos].dp;
posst = v[i][pos].pos;
}
return total;
}
int update(int I, int y) {
++ up_cnt;
if (up_cnt % rad == 0) {
refa_bucketuri();
}
// sterg i
int ind = bucket[I], pos = -1;
for (int i = 0; i < sz[ind]; ++ i)
if (v[ind][i].ind == I)
pos = i;
for (int i = pos; i < sz[ind] - 1; ++ i)
v[ind][i] = v[ind][i + 1];
-- sz[ind];
compute(ind);
//caut bucket nou
ind = 0;
while (ind + 1 < nrb && v[ind + 1][0].x <= y)
++ ind;
pos = 0;
while (pos < sz[ind] && v[ind][pos].x <= y)
++ pos;
// inserez in ind, pos
for (int i = sz[ind] - 1; i >= pos; -- i)
v[ind][i + 1] = v[ind][i];
v[ind][pos].x = y;
v[ind][pos].ind = I;
bucket[I] = ind;
++ sz[ind];
compute(ind);
return solve();
}
