#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());
// #define int long long
// #define int unsigned long long
// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>
// const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 5 * 1e5 + 15;
int t[8 * maxN], lazy[8 * maxN];
void prop(int v, int tl, int tr) {
t[v] += lazy[v];
if (tl != tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
} lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, int add) {
if (lazy[v]) prop(v, tl, tr);
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) {
lazy[v] += add; prop(v, tl, tr); return;
} int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, min(r, tm), add);
update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, add);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
vector<pii> arr;
for (int i = 0; i < a.size(); i++) arr.pb({a[i], i});
for (int i = 0; i < x.size(); i++) arr.pb({v[i], x[i]});
sort(all(arr)); int m = arr.size();
for (int i = 0; i < a.size(); i++) {
int pos = lower_bound(all(arr), make_pair(a[i], i)) - arr.begin() + 1;
update(1, 1, m, pos, pos, i);
update(1, 1, m, pos + 1, m, -1);
}
vector<int> ans(x.size());
for (int i = 0; i < x.size(); i++) {
int pos = lower_bound(all(arr), make_pair(a[x[i]], x[i])) - arr.begin() + 1;
update(1, 1, m, pos, pos, -x[i]);
update(1, 1, m, pos + 1, m, 1);
a[x[i]] = v[i];
pos = lower_bound(all(arr), make_pair(a[x[i]], x[i])) - arr.begin() + 1;
update(1, 1, m, pos, pos, x[i]);
update(1, 1, m, pos + 1, m, -1);
ans[i] = t[1];
}
return ans;
}
