//Huyduocdithitp
#include <bits/stdc++.h>
#include "bubblesort2.h"
typedef int ll;
#define pii pair<ll, ll>
#define MP make_pair
#define fi first
#define se second
#define TASK "mansion"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 500005
#define M 1000006
#define LOG 18
#define endl '\n'
using namespace std;
bool ghuy4g;
ll S;
ll n, q, a[N], m, st[6 * M], f[6 * M];
pii qr[N];
vector<pii> ns;
set<ll> s[2000006];
ll bit[M * 2];
void upd(ll u, ll v) {
ll idx = u;
while (idx <= m) {
bit[idx] += v;
idx += idx & (-idx);
}
}
ll get(ll u) {
ll idx = u, ans = 0;
while (idx > 0) {
ans += bit[idx];
idx -= idx & (-idx);
}
return ans;
}
ll gm(ll id) {
if (s[id].size() == 0) return 0;
else return *s[id].rbegin();
}
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = gm(l) - 1 - get(l - 1);
return;
}
ll mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
void pre() {
sort(ns.begin(), ns.end());
ns.resize(unique(ns.begin(), ns.end()) - ns.begin());
m = ns.size();
for (int i = 1; i <= n; i ++) {
a[i] = lower_bound(ns.begin(), ns.end(), make_pair(a[i], i)) - ns.begin() + 1;
upd(a[i], 1);
//cout << a[i] << " ";
s[a[i]].insert(i);
}
//cout << endl;
for (int i = 1; i <= q; i ++) {
qr[i].se = lower_bound(ns.begin(), ns.end(), make_pair(qr[i].se, qr[i].fi)) - ns.begin() + 1;
//cout << qr[i].fi << " " << qr[i].se << endl;
}
build(1, 1, m);
}
void lazy(ll id) {
if (f[id] == 0) return;
st[id] += f[id];
if (id * 2 < 4 * N) {
f[id * 2] += f[id];
}
if (id * 2 + 1 < 4 * N) {
f[id * 2 + 1] += f[id];
}
f[id] = 0;
}
void update(ll id, ll l, ll r, ll L, ll R, ll v) {
lazy(id);
if (l > R || r < L) return;
if (L <= l && r <= R) {
f[id] += v;
lazy(id);
return;
}
ll mid = (l + r) / 2;
update(id * 2, l, mid, L, R, v);
update(id * 2 + 1, mid + 1, r, L, R, v);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
void update1(ll id, ll l, ll r, ll i, ll v) {
lazy(id);
if (i > r || i < l || l > r) return;
if (l == r) {
st[id] = v;
return;
}
ll mid = (l + r) / 2;
update1(id * 2, l, mid, i, v);
update1(id * 2 + 1, mid + 1, r, i, v);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
vector<int> answer;
void solve() {
for (int id = 1; id <= q; id ++) {
ll i = qr[id].fi, v = qr[id].se;
ll o_v = a[i], n_v = v;
a[i] = n_v;
if (o_v == n_v) {
//cout << max(0, st[1]) << endl;
answer.push_back(max(0, st[1]));
continue;
}
//cout << i << " " << o_v << " " << n_v << endl;
upd(o_v, -1);
upd(n_v, 1);
s[o_v].erase(i);
update1(1, 1, m, o_v, gm(o_v) - get(o_v - 1) - 1);
s[n_v].insert(i);
update1(1, 1, m, n_v, gm(n_v) - get(n_v - 1) - 1);
if (o_v < n_v) {
// o_v + 1 -> n_v - 1
update(1, 1, m, o_v + 1, n_v - 1, 1);
}
else {
update(1, 1, m, n_v + 1, o_v - 1, -1);
}
//cout << max(0, st[1]) << endl;
answer.push_back(max(0, st[1]));
}
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
//cin >> n >> q;
n = A.size(), q = X.size();
for (int i = 1; i <= n; i ++) {
//cin >> a[i];
a[i] = A[i - 1];
ns.push_back({a[i], i});
}
for (int i = 1; i <= q; i ++) {
//cin >> qr[i].fi >> qr[i].se;
qr[i].fi = X[i - 1];
qr[i].se = V[i - 1];
qr[i].fi ++ ;
//cout << qr[i].fi << " | " << qr[i].se << endl;
ns.push_back({qr[i].se, qr[i].fi});
}
pre();
solve();
return answer;
}
bool klinh;
/*signed main(void) {
faster;
//countScans();
cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
return 0;
}*/
