#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> innterCountScans(vector<ll> a, vector<int> pos, vector<ll> value) {
int n = (int) a.size();
int q = (int) pos.size();
for (int i = 0; i < n; i++) {
a[i] = a[i] * (ll) (n + 1) + i;
}
assert(q == (int) value.size());
for (int it = 0; it < q; it++) {
value[it] = value[it] * (ll) (n + 1) + pos[it];
}
vector<int> sol;
for (int it = 0; it < q; it++) {
a[pos[it]] = value[it];
ll MN = a[n - 1];
int MX = 0;
for (int i = n - 1; i >= 0; i--) {
MN = min(MN, a[i]);
if (a[i] == MN) {
int bigger = 0;
for (int j = 0; j < i; j++) {
if (a[j] > a[i]) {
bigger++;
}
}
/// a[i] = minim pe sufix => (a[i] - 1)
MX = max(MX, bigger);
}
}
sol.push_back(MX);
}
return sol;
}
vector<int> countScans(vector<int> a, vector<int> b, vector<int> c) {
vector<ll> X, Z;
for (auto &it : a) {
X.push_back(it);
}
for (auto &it : c) {
Z.push_back(it);
}
return innterCountScans(X, b, Z);
}
