#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define pb push_back
typedef vector<int> vi;
const int MAXN = 500100;
int n, l;
//set<int> pos;
//map<int, int> cnt;
int x[MAXN];
int c;
vi srt;
int qCnt = 0;
int inBucket[MAXN];
int ids[510][510];
int j[510][510]; /// kiek kameru reiks, jei nuo kazkurio pradedam
int to[510][510]; /// kur tada baigsis intervalas visas
int last[510][510]; /// paskutinis id to intervalo
int sz[510];
int bucketCnt = 0;
void updateBucket (int b) {
int t = sz[b]-1;
for (int i = sz[b]-1; i >= 0; i--) {
while (ids[b][t] - ids[b][i] > l) {t--;}
/// ant ids[b][t] dar patenka, jei dedam ant ids[b][i]
if (t < sz[b]-1) {
j[b][i] = j[b][t+1] + 1;
last[b][i] = last[b][t+1];
} else {
j[b][i] = 1;
last[b][i] = ids[b][i];
}
to[b][i] = last[b][i] + l;
// cout <<" bucket b=" << b << " i = " << i << " ids = " << ids[b][i] /*<< " pos = " << x[ids[b][i]]*/
// << " j = " << j[b][i] << " last = " << last[b][i] << " to = " << to[b][i] << endl;
}
}
void updateAll () {
//cout << " updating all" << endl;
FOR(i, 0, bucketCnt-1) {
FOR(j, 0, sz[i]-1) {
srt.pb(ids[i][j]);
ids[i][j] = -1;
}
sz[i] = 0;
}
bucketCnt = 0;
int curBucket = 0;
for (int id : srt) {
if (sz[curBucket] >= c) {
curBucket++;
}
int where = sz[curBucket];
ids[curBucket][where] = id;
sz[curBucket]++;
// inBucket[id] = curBucket;
}
bucketCnt = curBucket+1;
srt.clear();
FOR(i, 0, bucketCnt-1) {
updateBucket (i);
}
}
int countCameras () {
int ret = 0;
int lst = -l-5;
FOR(b, 0, bucketCnt-1) {
if (sz[b] == 0) continue;
if (ids[b][sz[b]-1] - lst <= 0) continue;
int le = 0, ri = sz[b]-1;
while (le < ri) {
int mid = (le+ri)/2;
if (ids[b][mid] - lst > 0) ri = mid;
else le = mid+1;
}
ret += j[b][le];
lst = to[b][le];
}
return ret;
}
void rem (int id) {
int lst = 0;
for (int b = 0; b < bucketCnt; b++) {
if (sz[b] > 0) {
lst = b;
break;
}
}
for (int b = 0; b < bucketCnt; b++) {
if (sz[b] > 0) {
if (ids[b][0] > x[id]) break;
lst = b;
}
}
//int lst = inBucket[id];
bool was = false;
for (int i = 0; i < sz[lst]-1; i++) {
if (ids[lst][i] >= x[id]) was= true;
if (!was) continue;
//if (x[ids[lst][i]] < x[id]) continue;
swap(ids[lst][i],ids[lst][i+1]);
}
ids[lst][sz[lst]-1] = -1;
sz[lst]--;
updateBucket(lst);
}
void add (int id) {
int lst = 0;
for (int b = 0; b < bucketCnt; b++) {
if (sz[b] > 0) {
lst = b;
break;
}
}
for (int b = 0; b < bucketCnt; b++) {
if (sz[b] > 0) {
if (ids[b][0] > x[id]) break;
lst = b;
}
}
inBucket[id] = lst;
ids[lst][sz[lst]] = x[id];
for (int i = sz[lst]; i > 0; i--)
if (ids[lst][i-1] > ids[lst][i])
swap(ids[lst][i-1], ids[lst][i]);
sz[lst]++;
updateBucket(lst);
}
void init(int N, int L, int X[])
{
FOR(i,0,510-1) FOR(j, 0, 510-1) {
ids[i][j] = -1;
}
n = N;
c = sqrt(n);
l = L;
FOR(i, 0, N-1) {
// cnt[X[i]]++;
//pos.insert(X[i]);
x[i] = X[i];
srt.pb(x[i]);
}
//for (int id : srt)cout << " " << id;
//cout << endl;
updateAll();
}
int update(int i, int y)
{
qCnt++;
if (qCnt > c) {
updateAll();
// cout << " updupd" << endl;
qCnt = 0;
}
//cout << " removing i= " << i << endl;
rem (i);
x[i] = y;
//cout << " adding i=" << i << endl;
add (i);
return countCameras();
}
/*
3 10 3
50
61
71
2 61 2
1 50 2
0 40 2
4 10 6
0
0
0
0
0 10 1
0 0 1
2 11 2
0 11 2
1 11 2
3 11 1
4 10 5
10
15
17
20
2 16 1
1 25 2
3 35 2
0 38 2
2 0 3
4 10 0
7
17
20
32
2 1 7
0
100
0 99 1
0 98 2
1 97 1
1 98 1
1 99 1
1 100 2
1 98 1
2 1 5
50
50
0 49 1
0 50 1
1 48 2
0 49 1
0 47 1
*/
