#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int mxn = 1e6+10;
int st[1<<21], lz[1<<21];
pii pos[mxn];
int bit[mxn];
void add(int i, int v){
for(i++; i < mxn; i+=i&-i)
bit[i] += v;
}
int get(int i){
int res = 0;
for(i++; i > 0; i-=i&-i)
res += bit[i];
return res;
}
void push(int i){
if(lz[i]){
st[i<<1] += lz[i], lz[i<<1] += lz[i];
st[i<<1|1] += lz[i], lz[i<<1|1] += lz[i];
lz[i] = 0;
}
}
void pointSet(int i, int l, int r, int k, int v){
if(l==r){st[i] += v; return;}
int m = (l+r)>>1; push(i);
if(k <= m) pointSet(i<<1,l,m,k,v);
else pointSet(i<<1|1,m+1,r,k,v);
st[i] = max(st[i<<1],st[i<<1|1]);
}
void RangeAdd(int i, int l, int r, int s, int e, int v){
if(r < s || l > e) return;
if(s <= l && r <= e){st[i]+=v,lz[i]+=v; return;}
int m = (l+r)>>1; push(i);
RangeAdd(i<<1,l,m,s,e,v);
RangeAdd(i<<1|1,m+1,r,s,e,v);
st[i] = max(st[i<<1],st[i<<1|1]);
}
vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int N = (int) A.size();
int Q = (int) X.size();
for(int i = 0; i < N; i++)
pos[i] = {A[i],i};
for(int i = 0; i < Q; i++)
pos[i+N] = {V[i],X[i]};
sort(pos,pos+N+Q);
int M = unique(pos,pos+N+Q)-pos;
for(int i = 0; i < N; i++){
auto it = lower_bound(pos,pos+M,pii{A[i],i}) - pos;
pointSet(1,0,M-1,it,i);
add(it,1);
RangeAdd(1,0,M-1,it+1,M-1,-1);
}
vector<int> res(Q);
for(int t = 0; t < Q; t++){
int i = X[t];
auto it = lower_bound(pos,pos+M,pii{A[i],i}) - pos;
RangeAdd(1,0,M-1,it+1,M-1,1);
add(it,-1);
pointSet(1,0,M-1,it,-i);
A[i] = V[t];
it = lower_bound(pos,pos+M,pii{A[i],i}) - pos;
pointSet(1,0,M-1,it,i);
add(it,1);
RangeAdd(1,0,M-1,it+1,M-1,-1);
res[t] = st[1];
}
return res;
}
