#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
typedef pair<int,int> pii;
vector<int>bit(100000);
int m;
void upd(int pos,int val){
for(int i=pos;i<=m;i+=i&(-i))bit[i]+=val;
}
int query(int pos){
int res = 0;
while(pos){
res+=bit[pos];
pos-=pos&(-pos);
}
return res;
}
vector<int> countScans(vector<int> a,vector<int> x,vector<int>v){
int q=sz(x);
int n = sz(a);
vector<int> answer(q);
vector<int>b;
for(int i=0;i<n;i++)b.push_back(a[i]);
for(int i=0;i<q;i++)b.push_back(v[i]);
sort(all(b));
b.resize(unique(all(b))-b.begin());
m = sz(b);
for(int i=0;i<n;i++)a[i] = lower_bound(all(b),a[i])-b.begin()+1;
for(int i=0;i<q;i++)v[i] = lower_bound(all(b),v[i])-b.begin()+1;
for (int j=0;j<q;j++) {
for(int i=1;i<=m;i++)bit[i] = 0;
a[x[j]] = v[j];
int mx = 0;
for(int i=0;i<n;i++){
mx = max(mx,query(m)-query(a[i]));
upd(a[i],1);
}
answer[j] = mx;
}
return answer;
}
