#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)
using namespace std;
template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2>
void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}
template<class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}
template<class T>
void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
struct seg{
vector<int> ma, laz;
int n;
seg(int _n = 0){
n = _n;
ma.resize(4 * n + 3, 0);
laz.resize(4 * n + 3, 0);
}
void push(int i){
int t = laz[i];
laz[i] = 0;
ma[i * 2] += t;
ma[i * 2 + 1] += t;
laz[i * 2] += t;
laz[i * 2 + 1] += t;
}
void upd(int i, int l, int r, int u, int v, int c){
if(r < u || v < l) return;
if(u <= l && r <= v){
ma[i] += c;
laz[i] += c;
return;
}
push(i);
int m = (l + r) >> 1;
upd(i * 2, l, m, u, v, c);
upd(i * 2 + 1, m + 1, r, u, v, c);
ma[i] = max(ma[i * 2], ma[i * 2 + 1]);
}
void upd(int u, int v, int c){
upd(1, 0, n - 1, u, v, c);
}
int get(){
return ma[1];
}
};
const int MAX = 5e5 + 10;
int N, Q;
int a[MAX];
vector<pair<int, int>> queries;
set<int> st[MAX * 2];
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
N = sz(A);
Q = sz(X);
vector<int> ord;
for(int i = 1; i <= N; i++){
a[i] = A[i - 1];
ord.push_back(a[i]);
}
for(int i = 1; i <= Q; i++){
int p = X[i - 1], x = V[i - 1];
p++;
queries.push_back({p, x});
ord.push_back(x);
}
cps(ord);
for(int i = 1; i <= N; i++){
a[i] = lower_bound(ALL(ord), a[i]) - ord.begin();
st[a[i]].insert(i);
}
seg it(sz(ord));
for(int i = 0; i < sz(ord); i++){
st[i].insert(-INF);
it.upd(i, i, *st[i].rbegin());
it.upd(i, sz(ord) - 1, -(sz(st[i]) - 1));
}
vector<int> ans;
for(auto &o: queries){
o.se = lower_bound(ALL(ord), o.se) - ord.begin();
int p = o.fi, c = o.se;
it.upd(a[p], a[p], -*st[a[p]].rbegin());
st[a[p]].erase(p);
it.upd(a[p], a[p], *st[a[p]].rbegin());
it.upd(a[p], sz(ord) - 1, 1);
a[p] = c;
it.upd(a[p], a[p], -*st[a[p]].rbegin());
st[a[p]].insert(p);
it.upd(a[p], a[p], *st[a[p]].rbegin());
it.upd(a[p], sz(ord) - 1, -1);
ans.push_back(it.get());
}
return ans;
}
//int main(){
// ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("mst.inp","r",stdin);
// freopen("mst.out","w",stdout);
// int t = 1;
//// cin >> t;
// while(t--){
// solve();
// }
// return 0;
//}
