#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
int sz, seg[4 * N], lz[4 * N];
void init(int n) {
sz = 1;
while (sz < n) sz <<= 1;
}
void push(int x, int lx, int rx) {
if (!lz[x]) return;
seg[2 * x + 1] += lz[x], seg[2 * x + 2] += lz[x];
lz[2 * x + 1] += lz[x], lz[2 * x + 2] += lz[x];
lz[x] = 0;
}
void upd(int l, int r, int v, int x = 0, int lx = 0, int rx = sz) {
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
seg[x] += v, lz[x] += v;
return;
}
push(x, lx, rx);
int mid = (lx + rx) >> 1;
upd(l, r, v, 2 * x + 1, lx, mid);
upd(l, r, v, 2 * x + 2, mid, rx);
seg[x] = max(seg[2 * x + 1], seg[2 * x + 2]);
}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
int n = a.size(), q = x.size(), m;
vector<pair<int, int>> b;
for (int i = 0; i < n; ++i)
b.push_back({a[i], i});
for (int i = 0; i < q; ++i)
b.push_back({v[i], x[i]});
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end()) - b.begin());
m = b.size();
for (int i = 0; i < n; ++i)
a[i] = lower_bound(b.begin(), b.end(), make_pair(a[i], i)) - b.begin();
for (int i = 0; i < q; ++i)
v[i] = lower_bound(b.begin(), b.end(), make_pair(v[i], x[i])) - b.begin();
init(m);
for (int i = 0; i < n; ++i) {
upd(a[i], a[i] + 1, i);
upd(a[i] + 1, m, -1);
}
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
upd(a[x[i]], a[x[i]] + 1, -x[i]);
upd(a[x[i]] + 1, m, 1);
a[x[i]] = v[i];
upd(a[x[i]], a[x[i]] + 1, x[i]);
upd(a[x[i]] + 1, m, -1);
ans[i] = seg[0];
}
return ans;
}
