#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int k_N = 15e4 + 3;
int n, l;
int *x;
multiset<int> s;
set<int> s_start;
int start, ans;
void init(int N, int L, int X[]){
n = N;
l = L;
x = X;
for(int i = 0; i < n; ++i)
s.insert(x[i]);
start = *s.begin(), ans = 1;
s_start.insert(start);
for(int u: s){
if(u - start > l){
start = u;
ans++;
s_start.insert(start);
}
}
}
int update(int idx, int y){
//cout << ans << " - 1 stage" << endl;
s.erase(s.find(x[idx]));
if(s_start.count(x[idx])){
s_start.erase(x[idx]);
ans--;
auto it = s.lower_bound(x[idx]);
start = -l - 1;
for(; it != s.end(); ++it){
if(*it - start > l){
if(s_start.count(*it))
break;
s_start.insert(*it);
start = *it;
ans++;
}
else{
if(s_start.count(*it)){
ans--;
s_start.erase(*it);
}
}
}
}
x[idx] = y;
s.insert(x[idx]);
//cout << ans << " - 2 stage" << endl;
auto it2 = s_start.upper_bound(x[idx]);
bool ok = (it2 == s_start.begin());
if(it2 != s_start.begin()){
it2--;
if(x[idx] - *it2 > l)
ok = true;
}
if(ok){
auto it = s.lower_bound(x[idx]);
start = -l - 1;
for(; it != s.end(); ++it){
if(*it - start > l){
if(s_start.count(*it))
break;
s_start.insert(*it);
start = *it;
ans++;
}
else{
if(s_start.count(*it)){
ans--;
s_start.erase(*it);
}
}
}
}
//cout << ans << " - 3 stage" << endl;
return ans;
}
/*
4 4 3
3 4 6 7
0 5 1
3 9 2
3 8 1
*/
