#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
template <class X, class Y>
inline bool maximize(X &x, Y y) {
return (x < y ? x = y, true : false);
}
template <class X, class Y>
inline bool minimize(X &x, Y y) {
return (x > y ? x = y, true : false);
}
template <class X>
inline void compress(vector<X> &a) {
sort(all(a));
a.resize(unique(all(a)) - a.begin());
}
int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
return l + abs((ll) rng()) % (r - l + 1);
}
const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 1e9 + 7;
const int mxn = 1e6 + 5, LOG = 50;
void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
struct Seg {
int n;
vector<int> st, lz;
Seg(int n) : n(n) {
lz.resize(n << 2); st.resize(n << 2);
}
void setOne(int i, int d) {
st[i] += d;
lz[i] += d;
}
void down(int i) {
if (!lz[i])
return;
setOne(2 * i, lz[i]);
setOne(2 * i + 1, lz[i]);
lz[i] = 0;
}
void upd(int i, int l, int r, int u, int v, int d) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
return setOne(i, d);
}
down(i);
int m = (l + r) >> 1;
upd(2 * i, l, m, u, v, d);
upd(2 * i + 1, m + 1, r, u, v, d);
st[i] = max(st[2 * i], st[2 * i + 1]);
}
void upd(int u, int v, int d) {
if (u > v) return;
return upd(1, 1, n, u, v, d);
}
void change(int p, int val) {
int i = 1;
for (int l = 1, r = n; l < r; ) {
down(i);
int m = (l + r) >> 1;
if (p > m) {
l = m + 1;
i = 2 * i + 1;
}
else {
r = m;
i = 2 * i;
}
}
st[i] = val;
while (i > 1) {
i >>= 1;
st[i] = max(st[2 * i], st[2 * i + 1]);
}
}
int get(int i, int l, int r, int u, int v) {
if (l > v || r < u) return -inf;
if (l >= u && r <= v) return st[i];
down(i);
int m = (l + r) >> 1;
return max(get(2 * i, l, m, u, v), get(2 * i + 1, m + 1, r, u, v));
}
int get() {
return st[1];
}
};
set<int> s[mxn << 1];
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
int n = sz(A), q = sz(X);
vector<int> cps;
for (int i : A) cps.pb(i);
for (int i : V) cps.pb(i);
compress(cps);
for (int &i : A) i = lower_bound(all(cps), i) - cps.begin() + 1;
for (int &i : V) i = lower_bound(all(cps), i) - cps.begin() + 1;
int m = sz(cps);
forn(i, 0, n - 1) {
s[A[i]].insert(i + 1);
}
Seg seg(m);
forn(i, 1, m) {
seg.upd(i, i, *s[i].rbegin());
seg.upd(i, m, -sz(s[i]));
}
vector<int> ans(q);
forn(i, 0, q - 1) {
int p = X[i];
int value = V[i];
seg.upd(A[p], m, +1);
seg.upd(A[p], A[p], -(*s[A[p]].rbegin()));
s[A[p]].erase(p + 1);
if (sz(s[A[p]])) seg.upd(A[p], A[p], *s[A[p]].rbegin());
A[p] = value;
seg.upd(A[p], m, -1);
if (sz(s[A[p]])) seg.upd(A[p], A[p], -(*s[A[p]].rbegin()));
s[A[p]].insert(p + 1);
seg.upd(A[p], A[p], *s[A[p]].rbegin());
ans[i] = seg.get();
}
return ans;
}
//int main(void) {
//
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
//
// #define TASK "cquery"
// if (fopen(TASK".inp", "r")) {
// freopen(TASK".inp", "r", stdin);
// freopen(TASK".out", "w", stdout);
// }
//
// vector<int> A = {1, 2, 3, 4};
// vector<int> X = {0, 2};
// vector<int> V = {3, 1};
//
// for (int val : countScans(A, X, V))
// cout << val << '\n';
//
// return 0;
//}
