#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;
const int INF = 1e9;
struct segt {
int l, r;
segt *lc = NULL, *rc = NULL;
int x, lz;
segt(int l, int r) : l(l), r(r) {
x = -INF, lz = 0;
if (l < r) {
int m = (l + r) / 2;
lc = new segt(l, m);
rc = new segt(m + 1, r);
}
}
void put(int v) {
x += v;
lz += v;
}
void push() {
if (lz != 0)
lc->put(lz), rc->put(lz), lz = 0;
}
void add(int ql, int qr, int v) {
if (ql <= l && qr >= r) put(v);
else {
push();
if (qr <= lc->r) lc->add(ql, qr, v);
else if (ql >= rc->l) rc->add(ql, qr, v);
else lc->add(ql, qr, v), rc->add(ql, qr, v);
x = max(lc->x, rc->x);
}
}
};
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
vector<pii> v;
for (int i = 0; i < sz(A); i++) v.push_back({A[i], i});
for (int i = 0; i < sz(X); i++) v.push_back({V[i], X[i]});
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));
segt *tree = new segt(0, sz(v) - 1);
auto del = [&](int i) {
int p = lower_bound(begin(v), end(v), pii{A[i], i}) - begin(v);
tree->add(p, p, -INF - i);
if (p + 1 < sz(v)) tree->add(p + 1, sz(v) - 1, 1);
};
auto ins = [&](int i) {
int p = lower_bound(begin(v), end(v), pii{A[i], i}) - begin(v);
tree->add(p, p, INF + i);
if (p + 1 < sz(v)) tree->add(p + 1, sz(v) - 1, -1);
};
for (int i = 0; i < sz(A); i++) ins(i);
vector<int> ans(sz(X));
for (int i = 0; i < sz(X); i++) {
int p = X[i];
del(p);
A[p] = V[i];
ins(p);
ans[i] = tree->x;
}
return ans;
}
