#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "elephants.h"
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <array>
#include <algorithm>
#define ll long long
using namespace std;
unordered_map <ll, ll> mp;
unordered_map <ll, array<ll, 3>> nx;
ll G[500][10000], gsz[500];
ll V[500], sz, cur;
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 = 10*sqrt(q), t = 0;
mp.clear();
for (int i=0; i<n; ++i) A[i] = X[i], ++mp[A[i]];
ll s = 0;
for (int i=0; i<n; ++i) {
if (i != n-1 && A[i] == A[i+1]) continue;
G[sz][gsz[sz]++] = A[i];
if (s == 0) V[sz] = A[i];
++s;
if (s == rtn) s = 0, ++sz;
}
if (gsz[sz]) ++sz;
}
ll tail() {
ll u = sz-1;
while (true) {
if (gsz[u]) return G[u][gsz[u]-1];
else --u;
}
}
ll pv_it(ll z) {
if (z == -1) return tail();
while (z >= 0) {
if (gsz[z]) return G[z][gsz[z]-1];
else --z;
}
return -1;
}
ll nx_it(ll z) {
while (z < sz) {
if (gsz[z]) return G[z][0];
else ++z;
}
return -1;
}
ll lb(ll x, bool b) {
auto it = lower_bound(V, V+sz, x+1);
if (it == V) return -1;
it = prev(it);
ll z = it-V;
auto it2 = lower_bound(G[z], G[z]+gsz[z], x);
if (it2 != G[z]+gsz[z]) {
if (!b) return *it2;
else {
if (it2 != G[z]) return *prev(it2);
else if (z >= 0) return pv_it(z-1);
else return -1;
}
}
else {
if (!b) return nx_it(z+1);
else {
if (gsz[z]) return G[z][gsz[z]-1];
else if (z >= 0) return pv_it(z-1);
else return -1;
}
}
}
void ins(ll x) {
auto it = lower_bound(V, V+sz, x+1);
if (it == V) return;
it = prev(it);
ll z = it-V;
G[z][gsz[z]++] = x;
for (int i=0; i<gsz[z]; ++i) {
if (G[z][i] > G[z][gsz[z]-1]) swap(G[z][i], G[z][gsz[z]-1]);
}
}
void rmv(ll x) {
auto it = lower_bound(V, V+sz, x+1);
if (it == V) return;
it = prev(it);
ll z = it-V;
for (int i=0; i+1<gsz[z]; ++i) {
if (G[z][i] == x) swap(G[z][i], G[z][i+1]);
}
--gsz[z];
}
void update_nx(ll z, ll st, ll tar) {
ll id = gsz[z]-1, z2 = z, id2 = id;
while (true) {
//it = prev(it);
while (id < 0) {
if (z == 0) return;
if (st == -1) --z, id = gsz[z]-1;
else return;
}
while (true) {
while (id2 < 0) {
--z2, id2 = (ll)gsz[z2]-1;
}
if (G[z][id]+l <= G[z2][id2]) cur = G[z2][id2], --id2;
else break;
}
if (cur == -1 || G[z][id]+l > cur) {
if (G[z][id]+l > tail()) nx[G[z][id]] = {-1, 0, t};
}
else {
if (z == sz-1 || cur < V[z+1]) {
auto u = nx[cur];
nx[G[z][id]] = {u[0], u[1]+1, t};
//cout << "*" << G[z][id] << " " << tar << " " << nx[G[z][id]][0] << " " << nx[G[z][id]][1] << endl;
}
else if (st == -1 || G[z][id] >= tar) {
nx[G[z][id]] = {cur, 1, t};
//cout << "*" << G[z][id] << " " << tar << " " << nx[G[z][id]][0] << " " << nx[G[z][id]][1] << endl;
}
}
--id;
}
}
void reinit() {
cur = -1;
vector <ll> U;
for (int i=0; i<sz; ++i) {
for (int j=0; j<gsz[i]; ++j) U.push_back(G[i][j]);
}
for (int i=0; i<rtn+5; ++i) {
lazy[i] = {-1, -1};
gsz[i] = 0;
}
nx.clear();
sz = 0;
ll s = 0;
for (auto x : U) {
G[sz][gsz[sz]++] = x;
if (s == 0) V[sz] = x;
++s;
if (s == rtn) s = 0, ++sz;
}
if (gsz[sz]) ++sz;
V[0] = 0;
ll z = sz-1;
update_nx(z, -1, -1);
}
void add(ll x) {
//cout << "+" << x << endl;
cur = x;
++mp[x];
ins(x);
ll pv;
ll it = lb(x+l, 0);
if (it == -1) nx[x] = {-1, 0, t};
else {
auto vt = lower_bound(V, V+sz, x+1);
if (vt == V) return;
vt = prev(vt);
ll z = vt-V;
if (z == sz-1 || it < V[z+1]) nx[x] = {nx[it][0], nx[it][1]+1, t};
else nx[x] = {it, 1, t};
}
//cout << "*" << x << " " << nx[x][0] <<endl;
auto vt = lower_bound(V, V+sz, x-l+1);
if (vt == V) return;
vt = prev(vt);
ll z = vt-V;
ll it2 = lb(x, 1);
if (it2 == -1) return;
pv = it2;
update_nx(z, 0, pv-l+1);
--z;
while (z >= 0 && V[z] > pv-l) {
//cout << z << "?" << x << endl;
lazy[z] = {x, t};
--z;
}
if (z >= 0) {
cur = x;
update_nx(z, 0, pv-l+1);
}
}
void remove(ll x) {
//cout << "-" << x << endl;
mp.erase(x);
nx.erase(x);
rmv(x);
ll pv, nt;
ll it = lb(x, 0);
cur = nt = it;
it = lb(x, 1);
if (it == -1) return;
pv = it;
auto vt = lower_bound(V, V+sz, x-l+1);
if (vt == V) return;
vt = prev(vt);
ll z = vt-V;
update_nx(z, 0, pv-l+1);
--z;
while (z >= 0 && V[z] > pv-l) {
//cout << z << "?" << x << endl;
lazy[z] = {nt, t};
--z;
}
if (z >= 0) {
cur = nt;
update_nx(z, 0, pv-l+1);
}
}
ll query() {
ll f = 0, z = 0, u;
while (z < sz) {
if (gsz[z]) {
u = G[z][0];
break;
}
else ++z;
}
while (true) {
while (z != sz-1 && V[z+1] <= u) ++z;
//cout << u << "->" << nx[u][0] << " " << lazy[z][0] << endl;
if (nx[u][2] >= lazy[z][1]) {
f += nx[u][1];
if (nx[u][0] == -1) break;
u = nx[u][0];
}
else {
if (lazy[z][0] == -1) break;
u = lazy[z][0];
++f;
}
}
return f+1;
}
int update(int i, int y)
{
if (t % (2*rtq) == 0) {
++t;
reinit();
}
else ++t;
if (mp[A[i]] == 1) remove(A[i]);
else --mp[A[i]];
++t;
if (!mp.count(y)) add(y);
else ++mp[y];
A[i] = y;
return query();
}
