//#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > lis;
long long int seg[1<<21];
long long int lazy[1<<21];
void upd(int b){
seg[b]+=lazy[b];
if(b*2+2<(1<<21)){
lazy[b*2+1]+=lazy[b];
lazy[b*2+2]+=lazy[b];
}
lazy[b]=0;
}
inline void add(int b,int l,int r,int ll,int rr,long long int x){
upd(b);
if(r<=ll||rr<=l){
return;
}
if(ll<=l&&r<=rr){
lazy[b]+=x;
upd(b);
return;
}
add(b*2+1,l,(l+r)>>1,ll,rr,x);
add(b*2+2,(l+r)>>1,r,ll,rr,x);
seg[b]=max(seg[b*2+1],seg[b*2+2]);
}
int get_id(int pos,int val){
return lower_bound(lis.begin(),lis.end(),make_pair(val,pos))-lis.begin();
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
for(int i=0;i<A.size();i++){
lis.push_back(make_pair(A[i],i));
}
for(int i=0;i<X.size();i++){
lis.push_back(make_pair(V[i],X[i]));
}
sort(lis.begin(),lis.end());
lis.erase(unique(lis.begin(),lis.end()),lis.end());
for(int i=0;i<A.size();i++){
int z=get_id(i,A[i]);
add(0,0,lis.size(),z,z+1,i);
add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),-1);
}
vector<int> res;
for(int ii=0;ii<X.size();ii++){
int i=X[ii];
int z=get_id(i,A[i]);
add(0,0,lis.size(),z,z+1,-i);
add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),1);
A[i]=V[ii];
z=get_id(i,A[i]);
add(0,0,lis.size(),z,z+1,i);
add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),-1);
upd(0);
res.push_back(seg[0]+1);
}
return res;
}
