#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1<<21;
struct stree{
vector<int> lz,s,arr;
int sz;
void init(int n){
lz.resize(n,0);
s.resize(n,0);
arr.resize(n,0);
}
void pushlz(int l,int r,int idx){
if(!lz[idx]) return;
s[idx]+=lz[idx];
if(l!=r) lz[idx*2]+=lz[idx],lz[idx*2+1]+=lz[idx];
lz[idx]=0;
}
void build(int l,int r,int idx){
if(l==r){
s[idx]=arr[l];
return;
}
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
s[idx]=max(s[idx*2],s[idx*2+1]);
}
void update(int l,int r,int idx,int a,int b,int val){
if(a>b) return;
pushlz(l,r,idx);
if(b<l || a>r) return;
if(a<=l && b>=r){
lz[idx]+=val;
pushlz(l,r,idx);
return;
}
int m=(l+r)/2;
update(l,m,idx*2,a,b,val);
update(m+1,r,idx*2+1,a,b,val);
s[idx]=max(s[idx*2],s[idx*2+1]);
}
int query(int l,int r,int idx,int a,int b){
pushlz(l,r,idx);
if(a>r || b<l) return INT_MIN;
if(a<=l && b>=r) return s[idx];
int m=(l+r)/2;
return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
}
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int q=X.size();
int n=A.size();
std::vector<int> answer(q);
stree s;
s.init(N);
vector<pair<int,int>> v;
for(int i=0;i<n;i++){
int tmp=A[i];
v.push_back({tmp,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 m=v.size();
for(int i=0;i<n;i++){
A[i]=lower_bound(v.begin(),v.end(),make_pair(A[i],i))-v.begin();
//cout<<tmp <<" ";
}
//cout<<"\n";
for(int i=0;i<q;i++){
V[i]=lower_bound(v.begin(),v.end(),make_pair(V[i],X[i]))-v.begin();
}
for(int i=0;i<n;i++){
s.update(0,m-1,1,A[i],A[i],i);
s.update(0,m-1,1,A[i]+1,m-1,-1);
}
//for(int i=0;i<m;i++) cout<<s.query(0,m-1,1,i,i) <<" ";
//cout<<"\n";
for(int i=0;i<q;i++){
//change A[X[i]] to V[i]
s.update(0,m-1,1,A[X[i]],A[X[i]],-X[i]);
s.update(0,m-1,1,A[X[i]]+1,m-1,1);
A[X[i]]=V[i];
s.update(0,m-1,1,A[X[i]],A[X[i]],X[i]);
s.update(0,m-1,1,A[X[i]]+1,m-1,-1);
answer[i]=s.query(0,m-1,1,0,m-1);
}
return answer;
}
