#include "bubblesort2.h"
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
struct fenwick {
int n;
std::vector<int> tree;
fenwick() {}
fenwick(int n_) {
init(n_);
}
void init(int n_) {
n = n_;
tree.assign(n + 1, 0);
}
void modify(int p, int x) {
for (p += 1; p <= n; p += p & -p) {
tree[p] += x;
}
}
int get(int p) {
int res = 0;
for (p += 1; p; p -= p & -p) {
res += tree[p];
}
return res;
}
};
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
std::vector<int> ids(A.begin(), A.end());
ids.insert(ids.end(), V.begin(), V.end());
std::sort(ids.begin(), ids.end());
int n;
ids.resize(n = int(std::unique(ids.begin(), ids.end()) - ids.begin()));
fenwick fen;
int N = int(A.size());
int Q = int(X.size());
for (int i = 0; i < N; ++i) {
A[i] = int(std::lower_bound(ids.begin(), ids.end(), A[i]) - ids.begin());
}
for (int i = 0; i < Q; ++i) {
V[i] = int(std::lower_bound(ids.begin(), ids.end(), V[i]) - ids.begin());
}
std::vector<int> ans(Q);
for (int i = 0; i < Q; ++i) {
fen.init(n);
A[X[i]] = V[i];
int& res = ans[i];
for (int j = 0; j < N; ++j) {
int x = j - fen.get(A[j]);
res = std::max(res, x);
fen.modify(A[j], +1);
}
}
return ans;
}
