#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
int a,q;
vector <pair<int,int>> v;
int f[4000005];
int lazy[4000005];
void update(int id,int l,int r,int x,int y,int val){
if (x>r || y<l){
return;
}
if (l>=x && y>=r){
f[id]+=val;
lazy[id]+=val;
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,x,y,val);
update(id*2+1,mid+1,r,x,y,val);
f[id]=max(f[id*2],f[id*2+1])+lazy[id];
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
a=A.size();
q=X.size();
for (int i=0;i<a;i++){
v.push_back({A[i],i});
}
for (int i=0;i<q;i++){
v.push_back({V[i],X[i]});
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int n=v.size();
vector <int> res(q);
for (int i=0;i<a;i++){
int pos=lower_bound(v.begin(),v.end(),make_pair(A[i],i))-v.begin()+1;
update(1,1,n,pos,pos,i);
update(1,1,n,pos+1,n,-1);
}
for (int i=0;i<q;i++){
int x=X[i];
int y=V[i];
int pos=lower_bound(v.begin(),v.end(),make_pair(A[x],x))-v.begin()+1;
update(1,1,n,pos,pos,-x);
update(1,1,n,pos+1,n,1);
A[x]=y;
pos=lower_bound(v.begin(),v.end(),make_pair(A[x],x))-v.begin()+1;
update(1,1,n,pos,pos,x);
update(1,1,n,pos+1,n,-1);
res[i]=f[1];
// cout << res << "\n";
}
return res;
}
