#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
long long inf=1e9;
struct segtree{
long long info[4000005];
long long lz[4000005];
void apply(int st,int en,int i,long long val){
info[i]+=val;
lz[i]+=val;
}
void push(int st,int en,int i){
int m=(st+en)/2;
apply(st,m,i*2,lz[i]);
apply(m+1,en,i*2+1,lz[i]);
lz[i]=0;
}
void upd(int st,int en,int i,int l,int r,int val){
if(st>r||en<l)return;
//cerr<<"upd:"<<st<<" "<<en<<"\n";
if(st>=l&&en<=r)return apply(st,en,i,val);
push(st,en,i);
int m=(st+en)/2;
upd(st,m,i*2,l,r,val);
upd(m+1,en,i*2+1,l,r,val);
info[i]=max(info[i*2],info[i*2+1]);
}
int fans(int st,int en,int i,int l,int r){
if(st>r||en<l)return -inf;
if(st>=l&&en<=r)return info[i];
push(st,en,i);
int m=(st+en)/2;
return max(fans(st,m,i*2,l,r),fans(m+1,en,i*2+1,l,r));
}
void build(int st,int en,int i){
if(st==en)return info[i]=-inf,void();
int m=(st+en)/2;
build(st,m,i*2);
build(m+1,en,i*2+1);
info[i]=max(info[i*2],info[i*2+1]);
}
}tr;
int val[500005];
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
vector<pair<int,int>>v;
for(int i=0;i<A.size();i++)v.push_back({A[i],i+1}),val[i+1]=A[i];
for(int i=0;i<X.size();i++)v.push_back({V[i],X[i]+1});
sort(v.begin(),v.end());
//for(auto x:v)cerr<<x.first<<" "<<x.second<<"\n";
int x=v.size();
tr.build(1,x,1);
int N=A.size();
//cerr<<"x:"<<x<<"\n";
//cerr<<"work\n";
for(int i=0;i<v.size();i++){
tr.upd(1,x,1,i+1,i+1,v[i].second);
}
for(int i=1;i<=N;i++){
int pos=lower_bound(v.begin(),v.end(),make_pair(val[i],i))-v.begin()+1;
//cerr<<val[i]<<" "<<i<<"\n";
//cerr<<"pos:"<<pos<<"\n";
tr.upd(1,x,1,pos,pos,inf);
tr.upd(1,x,1,pos,x,-1);
/*cerr<<"ii:"<<i<<"\n";
for(int i=1;i<=x;i++)cerr<<tr.fans(1,x,1,i,i)<<" ";
cerr<<"\n";*/
}
//cerr<<"i:"<<0<<"\n";
//for(int i=1;i<=x;i++)cerr<<tr.fans(1,x,1,i,i)<<" ";
//cerr<<"\n";
//cerr<<"done\n";
//cerr<<"ans:"<<tr.fans(1,x,1,1,x)<<"\n";
//cerr<<"STT:\n";
vector<int>ans;
for(int i=0;i<X.size();i++){
int pos=lower_bound(v.begin(),v.end(),make_pair(A[X[i]],X[i]+1))-v.begin()+1;
tr.upd(1,x,1,pos,pos,-inf);
tr.upd(1,x,1,pos,x,+1);
A[X[i]]=V[i];
pos=lower_bound(v.begin(),v.end(),make_pair(A[X[i]],X[i]+1))-v.begin()+1;
tr.upd(1,x,1,pos,pos,inf);
tr.upd(1,x,1,pos,x,-1);
ans.push_back(tr.fans(1,x,1,1,x));
//cerr<<"i:"<<i<<"\n";
//for(int i=1;i<=x;i++)cerr<<tr.fans(1,x,1,i,i)<<" ";
//cerr<<"\n";
}
return ans;
}
