#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e6+50,inf=1e9;
void Unique(vector<int>&a){sort(a.begin(),a.end());a.resize(unique(a.begin(),a.end())-a.begin());}
int n,q,a[N];
set<int>st[N];
struct SegTree{
int root,nc,lc[2*N],rc[2*N],maks[2*N],lazy[2*N];
SegTree(){maks[0]=-inf;}
void update(int &c,int x){if(!c)c=++nc;maks[c]+=x;lazy[c]+=x;}
void push(int &c){if(!c)c=++nc;update(lc[c],lazy[c]);update(rc[c],lazy[c]);lazy[c]=0;}
void Update(int &c,int ss,int se,int qs,int qe,int x){
if(!c)c=++nc;
if(qs>qe||qe<ss||se<qs)return;
if(qs<=ss&&se<=qe){update(c,x);return;}
int mid=ss+se>>1;push(c);
Update(lc[c],ss,mid,qs,qe,x);Update(rc[c],mid+1,se,qs,qe,x);
maks[c]=max(maks[lc[c]],maks[rc[c]]);
}
int Get(int &c,int ss,int se,int qs,int qe){
if(!c)c=++nc;
if(qs>qe||qe<ss||se<qs)return -inf;
if(qs<=ss&&se<=qe)return maks[c];
int mid=ss+se>>1;push(c);
return max(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
}ST;
vector<int> countScans(vector<int>A,vector<int> X,vector<int> V){
n=A.size();q=X.size();
for(int i=1;i<=n;i++) a[i]=A[i-1];
for(auto &i:X) i++;
vector<int>vals;
for(int i=1;i<=n;i++) vals.pb(a[i]);
for(auto i:V) vals.pb(i);
Unique(vals);
for(int i=1;i<=n;i++) a[i]=lower_bound(vals.begin(),vals.end(),a[i])-vals.begin();
for(auto &i:V) i=lower_bound(vals.begin(),vals.end(),i)-vals.begin();
vector<int>res(q,0);
for(int i=1;i<=n;i++){
if(!st[a[i]].empty()){
ST.Update(ST.root,0,N,a[i],a[i],-*st[a[i]].rbegin());
}
st[a[i]].insert(i);
ST.Update(ST.root,0,N,a[i],a[i],*st[a[i]].rbegin());
ST.Update(ST.root,0,N,a[i],N,-1);
}
for(int I=0;I<q;I++){
int j=X[I];
ST.Update(ST.root,0,N,a[j],N,1);
ST.Update(ST.root,0,N,a[j],a[j],-*st[a[j]].rbegin());
st[a[j]].erase(j);
if(!st[a[j]].empty())ST.Update(ST.root,0,N,a[j],a[j],*st[a[j]].rbegin());
a[j]=V[I];
if(!st[a[j]].empty())ST.Update(ST.root,0,N,a[j],a[j],-*st[a[j]].rbegin());
st[a[j]].insert(j);
ST.Update(ST.root,0,N,a[j],a[j],*st[a[j]].rbegin());
ST.Update(ST.root,0,N,a[j],N,-1);
res[I]=ST.maks[ST.root];
}
return res;
}
