#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define endl "\n"
typedef long long int ll;
const int MOD = 1e9 + 7;
struct segTree{
vector<int> v;
vector<int> upd;
int siz;
void init(int n){
siz = 1;
while(siz < n) siz *= 2;
v.assign(2 * siz, 0);
upd.assign(2 * siz, 0);
}
void set(int l, int r, int u, int x, int lx, int rx){
if(lx >= l && rx <= r){
upd[x] += u;
v[x] += u;
return;
}
if(lx >= r || rx <= l) return;
int m = (lx + rx) / 2;
set(l, r, u, 2 * x + 1, lx, m);
set(l, r, u, 2 * x + 2, m, rx);
v[x] = max(v[2 * x + 1], v[2 * x + 2]) + upd[x];
}
void set(int l, int r, int u){
set(l, r, u, 0, 0, siz);
}
int get_ans(){
return v[0];
}
};
vector<int> countScans(vector<int> A,vector<int> V1,vector<int> V2){
int n = (int)A.size();
int q = (int)V1.size();
vector<int> all(n + q);
for(int i = 0; i < n; i++) all[i] = A[i];
for(int i = 0; i < q; i++) all[i + n] = V2[i];
sort(all.begin(), all.end());
unordered_map<int, int> m;
int curr = 0;
for(int i = 0; i < n + q; i++){
if(i == 0) {m[all[i]] = curr; curr++;}
else{
if(all[i] == all[i-1]) continue;
m[all[i]] = curr;
curr++;
}
}
segTree st; st.init(curr);
vector<set<int>> pos(curr);
for(int i = 0; i < n; i++){
pos[m[A[i]]].insert(i);
st.set(m[A[i]], curr, -1);
}
for(int i = 0; i < curr; i++){
if((int)pos[i].size() > 0){
st.set(i, i + 1, *pos[i].rbegin()+1);
}
}
vector<int> ans(q);
for(int qq = 0; qq < q; qq++){
int i = V1[qq];
int lst = A[i];
int nw = V2[qq];
A[i] = nw;
lst = m[lst];
nw = m[nw];
int lst_pos = *pos[lst].rbegin();
pos[lst].erase(i);
if((int)pos[lst].size() > 0) st.set(lst, lst + 1, (*pos[lst].rbegin() - lst_pos));
else st.set(lst, lst + 1, -lst_pos - 1);
st.set(lst, curr, 1);
if((int)pos[nw].size() == 0){
pos[nw].insert(i);
st.set(nw, nw + 1, i+1);
}else{
lst_pos = *pos[nw].rbegin();
pos[nw].insert(i);
st.set(nw, nw + 1, (*pos[nw].rbegin() - lst_pos));
}
st.set(nw, curr, -1);
ans[qq] = st.get_ans();
}
return ans;
}
