#include <bits/stdc++.h>
#include "bubblesort2.h"
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
const int N=5e5+3;
int n,a[N],b[N],sf[N];
int st[10*N],lazy[10*N],fw[N*10];
map<pair<int,int>,int> mp;
vector<pair<int,int>> vt;
void upd(int x,int y) {
while(x<=sz(vt)) {
fw[x]+=y;
x+=x&(-x);
}
}
int qr(int x) {
int ans=0;
while(x>0) {
ans+=fw[x];
x-=x&(-x);
}
return ans;
}
void push(int id) {
st[id*2]+=lazy[id];
st[id*2+1]+=lazy[id];
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
}
void build(int id,int l,int r) {
st[id]=-2e9;
if (l==r) return;
int mid=l+r>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int u,int v,int x) {
if (l>v || r<u) return;
if (l>=u && r<=v) {
st[id]+=x;
lazy[id]+=x;
return;
}
push(id);
int mid=l+r>>1;
update(id*2,l,mid,u,v,x);
update(id*2+1,mid+1,r,u,v,x);
st[id]=max(st[id*2],st[id*2+1]);
}
void update1(int id,int l,int r,int u,int x) {
if (l>u || r<u) return;
if (l==r) {
st[id]=x;
return;
}
push(id);
int mid=l+r>>1;
update1(id*2,l,mid,u,x);
update1(id*2+1,mid+1,r,u,x);
st[id]=max(st[id*2],st[id*2+1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V) {
n=sz(A);
vector<int> res;
For(i,1,n) a[i]=A[i-1];
For(i,1,n) vt.pb({a[i],i});
For(i,0,sz(X)-1) {
int x=X[i],v=V[i];
x++;
vt.pb({v,x});
}
sort(all(vt));
unq(vt);
For(i,0,sz(vt)-1) mp[vt[i]]=i+1;
For(i,1,n) {
int id=mp[{a[i],i}];
upd(id,1);
}
build(1,1,sz(vt));
For(i,1,n) {
int id=mp[{a[i],i}];
update1(1,1,sz(vt),id,i-qr(id));
}
For(i,0,sz(X)-1) {
int x=X[i],v=V[i];
x++;
int id=mp[{v,x}];
int id1=mp[{a[x],x}];
upd(id1,-1);
update1(1,1,sz(vt),id1,-2e9);
a[x]=v;
// if (i==0) cout << id1 << " " << id << endl;
upd(id,1);
if (id1<id) update(1,1,sz(vt),id1,id-1,1);
else if (id<id1) update(1,1,sz(vt),id,id1-1,-1);
update1(1,1,sz(vt),id,x-qr(id));
res.pb(st[1]);
}
// for(auto x: vt) cout << x.ff << " " << x.ss << endl;
//cout << st[1] << endl;
return res;
}
