#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=500050;
const int M=4*N;
int n,q,a[N],x[N],v[N],was[2*N];
int st[M],val[M],root,ls[M],rs[M],tsz,lzy[M];
void push(int c,int ss,int se){
if(ss!=se){
if(!ls[c])ls[c]=++tsz;
if(!rs[c])rs[c]=++tsz;
val[ls[c]]+=lzy[c];
val[rs[c]]+=lzy[c];
st[ls[c]]+=lzy[c];
st[rs[c]]+=lzy[c];
lzy[ls[c]]+=lzy[c];
lzy[rs[c]]+=lzy[c];
}
lzy[c]=0;
}
void Set(int&c,int ss,int se,int qs,int qe,int w){
if(!c)c=++tsz;
if(ss>se||ss>qe||se<qs)return;
if(qs<=ss&&se<=qe){st[c]+=w,lzy[c]+=w,val[c]+=w,push(c,ss,se);return;}
push(c,ss,se);
int mid=ss+se>>1;
Set(ls[c],ss,mid,qs,qe,w);
Set(rs[c],mid+1,se,qs,qe,w);
val[c]=-1e9;
if(ls[c])val[c]=max(val[c],val[ls[c]]);
if(rs[c])val[c]=max(val[c],val[rs[c]]);
}
void Act(int c,int ss,int se,int qi,int i){
if(ss==se){val[c]=(i==1?st[c]:-1e9);return;}
push(c,ss,se);
int mid=ss+se>>1;
if(qi<=mid)Act(ls[c],ss,mid,qi,i);
else Act(rs[c],mid+1,se,qi,i);
val[c]=max(val[ls[c]],val[rs[c]]);
}
void Input(vector<int> A,vector<int> X,vector<int> V){
n=A.size(),q=X.size();
vector<pair<int,int>> cpr;
for(int i=0;i<n;i++)cpr.pb({A[i],i});
for(int i=0;i<q;i++)cpr.pb({V[i],X[i]});
sort(cpr.begin(),cpr.end());
cpr.erase(unique(cpr.begin(),cpr.end()),cpr.end());
for(int i=0;i<n;i++)a[i]=(int)(lower_bound(cpr.begin(),cpr.end(),mp(A[i],i))-cpr.begin())+1;
for(int i=0;i<q;i++)v[i]=(int)(lower_bound(cpr.begin(),cpr.end(),mp(V[i],X[i]))-cpr.begin())+1;
for(int i=0;i<q;i++)x[i]=X[i];
}
void Print(int c,int ss,int se){
if(ss==se){if(ss<=10)printf("debug at %d == %d\n",ss,st[c]);return;}
int mid=ss+se>>1;
Print(ls[c],ss,mid);
Print(rs[c],mid+1,se);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
Input(A,X,V);
//for(int i=0;i<n;i++)printf("%d ",a[i]);puts("");
for(int i=0;i<n;i++)Set(root,1,2*N,a[i],a[i],i+1),was[a[i]]=1;
for(int i=0;i<q;i++)if(!was[v[i]])Set(root,1,2*N,v[i],v[i],x[i]+1),Act(root,1,2*N,v[i],0),was[v[i]]=1;
for(int i=0;i<n;i++)Set(root,1,2*N,a[i],2*N,-1);
for(int i=0;i<n;i++)Act(root,1,2*N,a[i],1);
//for(int i=0;i<n;i++)printf("%d ",a[i]);puts("");
vector<int> ans;
for(int i=0;i<q;i++){
Set(root,1,2*N,a[x[i]],2*N,1);
//Print(root,1,2*N);
Act(root,1,2*N,a[x[i]],0);
a[x[i]]=v[i];
//printf("ww %d\n",v[i]);
Set(root,1,2*N,a[x[i]],2*N,-1);
Act(root,1,2*N,a[x[i]],1);
ans.pb(val[root]);
}
return ans;
}
