#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using vi = vector<int>;
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)2e4+10;
int fen[mxN];
void upd(int x, int v){
for(; x<mxN; x+=x&-x) fen[x]+=v;
}
int sum(int x){ int s = 0; for(; x>0; x-=x&-x) s+=fen[x]; return s; }
int sum(int a, int b){
if(a>b) return 0;
return sum(b)-sum(a-1);
}
vi countScans(vi A, vi X, vi V){
int q = sz(X), n = sz(A); vi ans, a(all(A));
vector<int> v;
for(auto u : a) v.pb(u);
for(int i = 0; i < q; i++) v.pb(V[i]);
sort(all(v)); v.erase(unique(all(v)),end(v));
for(int i = 0; i < q; i++) V[i]=(int)(lower_bound(all(v),V[i])-begin(v))+1;
for(int i = 0; i < n; i++) a[i]=(int)(lower_bound(all(v),a[i])-begin(v))+1;
for(int _ = 0; _ < q; _++){
a[X[_]] = V[_];
int tot = 0; fill(fen,fen+mxN,0);
for(int i = 0; i < n; i++){
tot = max(tot, sum(a[i]+1,mxN-1));
upd(a[i],1);
}
ans.pb(tot);
}
return ans;
}
