#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
#define SZ(x) int(x.size())
#define lc (id<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define all(x) x.begin(), x.end()
#define pb push_back
const int MXN = 1e6+5;
int seg[MXN<<2], lz[MXN<<2], N;
void upd(int s, int e, int x, int l=0, int r=N, int id=1) {
if(s<=l && r<=e) {
seg[id] += x;
lz[id] += x;
return;
}
if(s<mid) upd(s, e, x, l, mid, lc);
if(e>mid) upd(s, e, x, mid, r, rc);
seg[id] = max(seg[lc], seg[rc]) + lz[id];
}
vector<int> cmp;
inline int GI(int x) { return lower_bound(all(cmp), x)-cmp.begin(); }
set<int> pos[MXN];
inline void erase(int i, int ai) {
upd(ai, N, 1);
if(i==(*pos[ai].rbegin()))
upd(ai, ai+1, -i + (*prev(prev(pos[ai].end()))));
pos[ai].erase(i);
}
inline void insert(int i, int ai) {
upd(ai, N, -1);
if(i>(*pos[ai].rbegin()))
upd(ai, ai+1, -(*pos[ai].rbegin())+i);
pos[ai].insert(i);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int n = SZ(A), q = SZ(X);
for(int i=0; i<n; i++) cmp.pb(A[i]);
for(int i=0; i<q; i++) cmp.pb(V[i]);
sort(all(cmp));
cmp.resize(unique(all(cmp))-cmp.begin());
N = SZ(cmp);
for(int i=0; i<N; i++) pos[i].insert(-1);
for(int i=0; i<n; i++) A[i] = GI(A[i]);
for(int i=0; i<q; i++) V[i] = GI(V[i]);
for(int i=0; i<n; i++) insert(i, A[i]);
vector<int> ans(q);
for(int i=0; i<q; i++) {
erase(X[i], A[X[i]]);
insert(X[i], A[X[i]]=V[i]);
ans[i] = seg[1];
}
return ans;
}
