#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int MOD = 998244353;
const int nx[4] = {-1, 0, 1, 0}, ny[4] = {0, 1, 0, -1};
const int MX = 2000005;
int ST[8000005], lazy[8000005], B[8000005];
void prop(int v, int l, int r) {
if(l == r || lazy[v] == 0)
return;
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
ST[v * 2] += lazy[v];
ST[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int l, int r, int lo, int hi, int val) {
prop(v, l, r);
if(l > hi || r < lo) return;
if(l >= lo && r <= hi) {
ST[v] += val;
lazy[v] += val; prop(v, l, r);
return;
}
update(v * 2, l, (l + r) / 2, lo, hi, val);
update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
}
void build(int v, int l, int r) {
if(l == r) {
ST[v] = B[l];
return;
}
build(v * 2, l, (l + r) / 2);
build(v * 2 + 1, (l + r) / 2 + 1, r);
ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
set<pair<int, int>> S; map<pair<int, int>, int> M;
int N = A.size(), Q = X.size();
for(int l = 0; l < N; l++) S.insert({A[l], l});
for(int l = 0; l < Q; l++) S.insert({V[l], X[l]});
int cur = 0;
for(auto u : S) M[u] = cur++;
for(int l = 0; l < N; l++) A[l] = M[{A[l], l}];
for(int l = 0; l < N; l++) B[A[l]] = l;
for(int l = 0; l < Q; l++) V[l] = M[{V[l], X[l]}];
build(1, 0, MX - 1);
for(int l = 0; l < N; l++)
update(1, 0, MX - 1, A[l] + 1, MX - 1, -1);
vector<int> res(Q);
for(int l = 0; l < Q; l++) {
int i = X[l];
int u = V[l], v = A[i];
update(1, 0, MX - 1, v + 1, MX - 1, 1);
update(1, 0, MX - 1, v, v, -i);
update(1, 0, MX - 1, u + 1, MX - 1, -1);
update(1, 0, MX - 1, u, u, i);
res[l] = ST[1];
A[i] = u;
}
return res;
}
