#include "bubblesort2.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000000
int n,q,seg[1<<21],la[1<<21],x[500005],p[500005],v[500005];
priority_queue<int>d[1000005];
set<int>u[1000005];
vector<int>cm;
map<int,int>pr;
void lazy(int l,int r,int k){
seg[k]+=la[k];
if(l!=r){
la[k*2+1]+=la[k];
la[k*2+2]+=la[k];
}
la[k]=0;
}
void add(int a,int b,int l,int r,int k,int x){
lazy(l,r,k);
if(r<a||b<l)return;
if(a<=l&&r<=b){
la[k]+=x;
lazy(l,r,k);
return;
}
add(a,b,l,(l+r-1)/2,k*2+1,x);
add(a,b,(l+r+1)/2,r,k*2+2,x);
seg[k]=max(seg[k*2+1],seg[k*2+2]);
}
int que(int a,int b,int l,int r,int k){
lazy(l,r,k);
if(r<a||b<l)return -INF;
if(a<=l&&r<=b)return seg[k];
return max(que(a,b,l,(l+r-1)/2,k*2+1),que(a,b,(l+r+1)/2,r,k*2+2));
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
vector<int>ans;
n=A.size();
q=X.size();
for(int i=0;i<n;i++){
x[i]=A[i];
cm.PB(x[i]);
}
for(int i=0;i<q;i++){
p[i]=X[i];
v[i]=V[i];
cm.PB(v[i]);
}
sort(cm.begin(),cm.end());
cm.erase(unique(cm.begin(),cm.end()),cm.end());
for(int i=0;i<cm.size();i++)pr[cm[i]]=i;
for(int i=0;i<n;i++)x[i]=pr[x[i]];
for(int i=0;i<q;i++)v[i]=pr[v[i]];
for(int i=0;i<cm.size();i++){
d[i].push(0);
u[i].insert(0);
}
for(int i=0;i<n;i++){
add(x[i],cm.size()-1,0,(1<<20)-1,0,-1);
d[x[i]].push(i+1);
u[x[i]].insert(i+1);
}
for(int i=0;i<cm.size();i++){
add(i,i,0,(1<<20)-1,0,d[i].top());
}
for(int i=0;i<q;i++){
int a=p[i],b=v[i];
if(x[a]==b){
ans.PB(que(0,cm.size(),0,(1<<20)-1,0));
continue;
}
add(x[a],cm.size()-1,0,(1<<20)-1,0,1);
add(b,cm.size()-1,0,(1<<20)-1,0,-1);
u[x[a]].erase(a+1);
if(d[x[a]].top()==a+1){
while(u[x[a]].find(d[x[a]].top())==u[x[a]].end())d[x[a]].pop();
add(x[a],x[a],0,(1<<20)-1,0,-(a+1)+d[x[a]].top());
}
x[a]=b;
u[b].insert(a+1);
if(d[b].top()<a+1){
add(b,b,0,(1<<20)-1,0,-d[b].top()+a+1);
}
d[b].push(a+1);
ans.PB(que(0,cm.size(),0,(1<<20)-1,0));
}
return ans;
}
