#include "bubblesort2.h"
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int inf=2e9;
int n, q, B[1<<20], lim;
vector<pii> comp;
struct node{
int mx, lz, cnt;
} tree[1<<21];
void lazy(int v, int val){
tree[v].mx-=val, tree[v].cnt+=val, tree[v].lz+=val;
}
void busy(int v, int s, int e){
int &z=tree[v].lz;
if(s!=e){
lazy(v*2, z);
lazy(v*2+1,z);
}
z=0;
}
void del(int v, int s, int e, int pos){
busy(v,s,e);
node &nd=tree[v];
if(s==e){
nd.mx=-nd.cnt;
return;
}
int m=(s+e)/2;
if(pos<=m){
lazy(v*2+1,-1);
del(v*2,s,m,pos);
}
else{
del(v*2+1,m+1,e,pos);
}
nd.mx=max(tree[v*2].mx, tree[v*2+1].mx);
}
void del(int pos){
del(1,1,lim,pos);
}
void add(int v, int s, int e, int pos, int idx){
busy(v,s,e);
node &nd=tree[v];
if(s==e){
nd.mx=idx-nd.cnt;
return;
}
int m=(s+e)/2;
if(pos<=m){
lazy(v*2+1,1);
add(v*2,s,m,pos,idx);
}
else{
add(v*2+1,m+1,e,pos,idx);
}
nd.mx=max(tree[v*2].mx, tree[v*2+1].mx);
}
void add(int pos, int idx){
add(1,1,lim,pos,idx);
}
int mx(){
return tree[1].mx;
}
void debug(int v=1, int s=1, int e=lim){
busy(v,s,e);
node &nd=tree[v];
if(s==e){ cout<<s<<": "<<nd.mx<<' '<<nd.cnt<<'\n'; return; }
int m=(s+e)/2;
debug(v*2,s,m);
debug(v*2+1,m+1,e);
}
int resp(int x, int pos){
return lower_bound(comp.begin(), comp.end(), pii({x,pos}))-comp.begin()+1;
}
vi countScans(vi A, vi X, vi V){
vi ans;
n=A.size(), q=X.size();
for(int i=0; i<n; i++) comp.push_back({A[i], i});
for(int i=0; i<q; i++) comp.push_back({V[i], X[i]});
sort(comp.begin(), comp.end());
lim=unique(comp.begin(), comp.end())-comp.begin();
comp.resize(lim);
for(int i=0; i<n; i++){
int val=resp(A[i], i);
B[i]=val;
add(val, i);
}
for(int ii=0; ii<q; ii++){
int val=resp(V[ii], X[ii]), idx=X[ii];
del(B[idx]);
B[idx]=val;
add(val, idx);
ans.push_back(mx());
}
return ans;
}
