#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;
ll G[500][5000], gsz[500];
array <ll, 2> nx[500][5000];
ll V[500], sz, cur;
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]];
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;
}
void update_nx(ll z) {
ll id = gsz[z]-1, id2 = id;
while (true) {
if (id < 0) return;
while (true) {
if (id2 > 0 && G[z][id]+l <= G[z][id2-1]) --id2;
else break;
}
if (G[z][id]+l > G[z][id2]) nx[z][id] = {id, 0};
else nx[z][id] = {nx[z][id2][0], nx[z][id2][1]+1};
//cout << G[z][id] << " " << G[z][id2] << " " << nx[z][id][0] << " " << nx[z][id][1] << endl;
--id;
}
}
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]);
}
update_nx(z);
}
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];
update_nx(z);
}
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) gsz[i] = 0;
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;
for (int i=0; i<sz; ++i) update_nx(i);
}
void add(ll x) {
//cout << "+" << x << endl;
++mp[x];
ins(x);
}
void remove(ll x) {
//cout << "-" << x << endl;
mp.erase(x);
rmv(x);
}
ll query() {
ll f = 0, u = -1e18;
for (int i=0; i<sz; ++i) {
if (!gsz[i] || u+l > G[i][gsz[i]-1]) continue;
for (int j=0; j<gsz[i]; ++j) {
if (u+l <= G[i][j]) {
f += nx[i][j][1]+1;
u = G[i][nx[i][j][0]];
break;
}
}
//cout << u << " " << f << endl;
}
//cout << endl;
return f;
}
int update(int i, int y)
{
if (t % rtq == 0) reinit();
++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();
}
