#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+100;
pair<int,int> t[N*4];
int add[N*4];
pair<int,int> operator +(const pair<int,int>&x,const pair<int,int>&y){
pair<int,int>res;
res.first=x.first+y.first;
res.second=max(x.second,y.second);
return res;
}
void build(int v,int tl,int tr){
if(tl==tr){
t[v]={0,0};
return;
}
int mid=(tl+tr)>>1ll;
build(v*2,tl,mid);
build(v*2+1,mid+1,tr);
t[v]=t[v*2]+t[v*2+1];
}
void push(int v,int tl,int tr){
if(tl!=tr){
add[v*2]+=add[v];
add[v*2+1]+=add[v];
}
t[v].second+=add[v];
add[v]=0;
}
void upd(int v,int tl,int tr,int l,pair<int,int>x){
push(v,tl,tr);
if(tl==tr){
t[v]=x;
return;
}
int mid=(tl+tr)>>1ll;
if(l<=mid){
upd(v*2,tl,mid,l,x);
push(v*2+1,mid+1,tr);
}
else{
upd(v*2+1,mid+1,tr,l,x);
push(v*2,tl,mid);
}
t[v]=t[v*2]+t[v*2+1];
}
void upd(int v,int tl,int tr,int l,int r,int x){
push(v,tl,tr);
if(tl>r||tr<l)return;
if(l<=tl&&tr<=r){
add[v]+=x;
push(v,tl,tr);
return;
}
int mid=(tl+tr)>>1ll;
upd(v*2,tl,mid,l,r,x);
upd(v*2+1,mid+1,tr,l,r,x);
t[v]=t[v*2]+t[v*2+1];
}
pair<int,int> get(int v,int tl,int tr,int l,int r){
push(v,tl,tr);
if(tl>r||tr<l)return {0,0};
if(l<=tl&&tr<=r)return t[v];
int mid=(tl+tr)>>1ll;
return get(v*2,tl,mid,l,r)+get(v*2+1,mid+1,tr,l,r);
}
vector<pair<int,int>>uni;
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
int q=x.size();
int n=a.size();
for(int i=0;i<n;i++){
uni.push_back({a[i],i});
}
for(int i=0;i<q;i++){
uni.push_back({v[i],x[i]});
}
sort(uni.begin(),uni.end());
uni.resize(unique(uni.begin(),uni.end())-uni.begin());
vector<int>ans(q);
build(1,0,uni.size()-1);
// cout<<uni.size()<<'\n';
for(int i=0;i<n;i++){
int pos=lower_bound(uni.begin(),uni.end(),make_pair(a[i],i))-uni.begin();
auto cur=get(1,0,uni.size()-1,0,pos-1);
upd(1,0,uni.size()-1,pos,{1,i-cur.first});
upd(1,0,uni.size()-1,pos+1,uni.size()-1,-1);
}
// cout<<t[1].second<<'\n';
for(int j=0;j<q;j++){
int pos=lower_bound(uni.begin(),uni.end(),make_pair(a[x[j]],x[j]))-uni.begin();
upd(1,0,uni.size()-1,pos,{0,0});
upd(1,0,uni.size()-1,pos+1,uni.size()-1,1);
a[x[j]]=v[j];
pos=lower_bound(uni.begin(),uni.end(),make_pair(a[x[j]],x[j]))-uni.begin();
auto cur=get(1,0,uni.size()-1,0,pos-1);
upd(1,0,uni.size()-1,pos,{1,x[j]-cur.first});
upd(1,0,uni.size()-1,pos+1,uni.size()-1,-1);
ans[j]=t[1].second;
}
return ans;
}
