#include "elephants.h"
#include <iostream>
#include <map>
#include <deque>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;
map <ll, ll> mp;
map <ll, array<ll, 3>> nx;
vector <ll> V;
deque <ll> dq;
array <ll, 2> lazy[400];
ll n, l, rtn, q = 150000, rtq, t, A[150000];
void init(int N, int L, int X[])
{
n = N, l = L+1, rtn = sqrt(n), rtq = sqrt(q), t = 0;
mp.clear();
for (int i=0; i<n; ++i) A[i] = X[i], ++mp[A[i]];
}
void update_nx(ll z, ll st, ll tar) {
auto it = mp.end();
if (st != -1) it = mp.lower_bound(st);
while (it != mp.begin()) {
it = prev(it);
while (z >= 0 && it->first < V[z]) {
if (st == -1) --z;
else break;
}
while (dq.size() > 1) {
auto u = dq.front();
dq.pop_front();
if (it->first+l <= dq.front()) continue;
else {
dq.push_front(u);
break;
}
}
if (dq.empty() || it->first+l > dq.front()) {
if (it->first+l > prev(mp.end())->first) nx[it->first] = {-1, 0, t};
}
else {
auto u = nx[dq.front()];
if (z == V.size()-1 || dq.front() < V[z+1]) {
nx[it->first] = {u[0], u[1]+1, t};
//cout << dq.front() << endl;
//cout << "*" << it->first << " " << tar << " " << nx[it->first][0] << " " << nx[it->first][1] << endl;
}
else if (st == -1 || it->first >= tar) {
nx[it->first] = {dq.front(), 1, t};
//cout << "*" << it->first << " " << tar << " " << nx[it->first][0] << " " << nx[it->first][1] << endl;
}
}
dq.push_back(it->first);
}
}
void reinit() {
while (!dq.empty()) dq.pop_back();
for (int i=0; i<rtn; ++i) lazy[i] = {-1, -1};
V.clear();
nx.clear();
ll s = 0;
for (auto [x, y] : mp) {
if (s == 0) V.push_back(x);
++s;
if (s == rtn) s = 0;
}
V[0] = 0;
ll z = V.size()-1;
update_nx(z, -1, -1);
/*for (auto u : V) cout << u << "#";
cout << endl;*/
}
void add(ll x) {
//cout << "+" << x << endl;
while (!dq.empty()) dq.pop_back();
dq.push_front(x);
++mp[x];
ll pv;
auto it = mp.lower_bound(x+l);
if (it == mp.end()) nx[x] = {-1, 0};
else nx[x] = {it->first, 1};
//cout << "*" << x << " " << nx[x][0] << endl;
auto vt = lower_bound(V.begin(), V.end(), x-l+1);
if (vt == V.begin()) return;
vt = prev(vt);
ll z = vt-V.begin();
auto it2 = mp.lower_bound(x);
if (it2 == mp.begin()) return;
pv = prev(it2)->first;
update_nx(z, (z == V.size()-1 ? (ll)1e18 : V[z+1]), pv-l+1);
--z;
while (z >= 0 && V[z] > pv-l) {
//cout << z << "?" << x << endl;
lazy[z] = {x, t};
--z;
}
if (z >= 0) {
while (!dq.empty()) dq.pop_back();
dq.push_front(x);
update_nx(z, (z == V.size()-1 ? (ll)1e18 : V[z+1]), pv-l+1);
}
}
void remove(ll x) {
//cout << "-" << x << endl;
while (!dq.empty()) dq.pop_back();
mp.erase(x);
nx.erase(x);
ll pv, nt;
auto it = mp.lower_bound(x);
if (it == mp.end()) nt = -1;
else {
nt = it->first;
dq.push_front(nt);
}
if (it == mp.begin()) return;
pv = prev(it)->first;
auto vt = lower_bound(V.begin(), V.end(), x-l+1);
if (vt == V.begin()) return;
vt = prev(vt);
ll z = vt-V.begin();
update_nx(z, (z == V.size()-1 ? (ll)1e18 : V[z+1]), pv-l+1);
--z;
while (z >= 0 && V[z] > pv-l) {
//cout << z << "?" << x << endl;
lazy[z] = {x, t};
--z;
}
if (z >= 0) {
while (!dq.empty()) dq.pop_back();
dq.push_front(nt);
update_nx(z, (z == V.size()-1 ? (ll)1e18 : V[z+1]), pv-l+1);
}
}
ll query() {
ll f = 0;
auto it = mp.begin();
while (it != mp.end()) {
auto vt = lower_bound(V.begin(), V.end(), it->first+1);
vt = prev(vt);
ll z = vt-V.begin();
//cout << it->first << " " << nx[it->first][1] << " " << lazy[z][0] << endl;
if (nx[it->first][2] >= lazy[z][1]) {
f += nx[it->first][1];
if (nx[it->first][0] == -1) break;
it = mp.find(nx[it->first][0]);
}
else {
if (lazy[z][0] == -1) break;
it = mp.find(lazy[z][0]);
++f;
}
}
return f+1;
}
int update(int i, int y)
{
if (t % rtq == 0) {
++t;
reinit();
}
else ++t;
if (mp[A[i]] == 1) remove(A[i]);
else --mp[A[i]];
if (!mp.count(y)) add(y);
else ++mp[y];
A[i] = y;
return query();
}
