#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=8005;
int n, q;
vector <int> sol;
vector <int> saz;
int F[2*N];
int query(int x) {
int ret=0;
for (; x>0; x-=x&-x) ret+=F[x];
return ret;
}
void update(int x, int val) {
for (; x<=n+q; x+=x&-x) F[x]+=val;
}
vector<int> countScans(vector<int> A, vector<int> XX, vector<int> V){
n=A.size();
q=V.size();
saz=V;
for (int x:A) saz.pb(x);
sort(saz.begin(), saz.end());
saz.erase(unique(saz.begin(), saz.end()), saz.end());
for (int i=0; i<n; ++i) A[i]=lower_bound(saz.begin(), saz.end(), A[i])-saz.begin()+1;
for (int i=0; i<q; ++i) V[i]=lower_bound(saz.begin(), saz.end(), V[i])-saz.begin()+1;
for (int i=0; i<q; ++i) {
A[XX[i]]=V[i];
memset(F, 0, sizeof F);
int maxi=0;
for (int j=0; j<n; ++j) {
int curr=j-query(A[j]);
maxi=max(maxi, curr);
update(A[j], 1);
}
sol.pb(maxi);
}
return sol;
}
