#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i< b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update> iset;
iset is;
ll solve(vector<int> A){
iset nis;
ll res = 0;
for(auto i:is){
nis.insert({i.snd,i.fst});
//cout<<i.snd<<" "<<ll(SZ(nis)-(nis.order_of_key({i.snd,i.fst})+1))<<'\n';
res=max((ll)res, ll(SZ(nis)-(nis.order_of_key({i.snd,i.fst})+1)));
}
return res;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
forn(i,0,SZ(A)) is.insert({i,A[i]});
iset nis;
vector<ll> cnt(SZ(A));
ll rres = 0;
for(auto i:is){
nis.insert({i.snd,i.fst});
//cout<<i.snd<<" "<<ll(SZ(nis)-(nis.order_of_key({i.snd,i.fst})+1))<<'\n';
cnt[i.fst]=ll(SZ(nis)-(nis.order_of_key({i.snd,i.fst})+1));
}
vector<int> nA = A;
vector<int> res;
forn(i,0,SZ(X)){
//is.erase(is.find({X[i],nA[X[i]]}));
//is.insert({X[i],nA[X[i]]});
rres=0;
cnt[X[i]]=0;
forn(j,0,SZ(A)){
if(j>X[i]){
if(nA[X[i]]>nA[j]){
if(V[i]<=nA[j]) cnt[j]--;
}else{
if(V[i]>nA[j]) cnt[j]++;
}
}else{
if(j!=X[i] && nA[j]>V[i]) cnt[X[i]]++;
}
//cout<<cnt[j]<<" ";
rres=max(rres,cnt[j]);
}
nA[X[i]]=V[i];
res.pb(rres);
}
return res;
}
