#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
int cate;
set<int> ofval[1000005];
map<int,int> mp,nrm;
int aint[2200000],lazy[2200000];
void propagate(int nod)
{
if(!lazy[nod])
return;
lazy[nod*2] += lazy[nod];
lazy[nod*2+1] += lazy[nod];
aint[nod*2] += lazy[nod];
aint[nod*2+1] += lazy[nod];
lazy[nod]=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
aint[nod] += newv;
lazy[nod] += newv;
return;
}
propagate(nod);
int mij=(st+dr)/2;
upd(nod*2,st,mij,le,min(mij,ri),newv);
upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
aint[nod] = max(aint[nod*2], aint[nod*2+1]);
}
void scoate_ult(int val)
{
if(ofval[val].empty())
return;
int ult = *ofval[val].rbegin();
ult++;
upd(1,1,cate,val,val,-ult);
}
void baga_ult(int val)
{
if(ofval[val].empty())
return;
int ult = *ofval[val].rbegin();
ult++;
upd(1,1,cate,val,val,+ult);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V)
{
for(int x:A)
mp[x]++;
for(int x:V)
mp[x]++;
for(auto it:mp)
if(it.second)
nrm[it.first]=++cate;
for(int&x:A)
x = nrm[x];
for(int&x:V)
x = nrm[x];
for(int i=0;i<A.size();i++)
{
ofval[A[i]].insert(i);
upd(1,1,cate,A[i],cate,-1);
}
for(int val=1;val<=cate;val++)
baga_ult(val);
vector<int> sol;
for(int i=0;i<X.size();i++)
{
int oldval = A[X[i]], newval = V[i];
scoate_ult(oldval);
scoate_ult(newval);
upd(1,1,cate,A[X[i]],cate,+1);
ofval[A[X[i]]].erase(X[i]);
A[X[i]] = V[i];
ofval[A[X[i]]].insert(X[i]);
upd(1,1,cate,A[X[i]],cate,-1);
baga_ult(oldval);
baga_ult(newval);
sol.push_back(aint[1]);
}
return sol;
}
