#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
array<int, 2> values[N];
int maxi[4 * N], lazy[4 * N], m;
void update(int a, int b, int x, int u = 1, int l = 0, int r = m - 1) {
if (a > b || b < l || r < a) {
return;
} else if (a <= l && r <= b) {
lazy[u] += x;
maxi[u] += x;
} else {
int m = (l + r) / 2;
update(a, b, x, 2 * u, l, m);
update(a, b, x, 2 * u + 1, m + 1, r);
maxi[u] = max(maxi[2 * u], maxi[2 * u + 1]) + lazy[u];
}
}
void assign(int a, int x, int u = 1, int l = 0, int r = m - 1) {
if (l == r) {
maxi[u] = x + lazy[u];
} else {
int m = (l + r) / 2;
if (a <= m) {
assign(a, x, 2 * u, l, m);
} else {
assign(a, x, 2 * u + 1, m + 1, r);
}
maxi[u] = max(maxi[2 * u], maxi[2 * u + 1]) + lazy[u];
}
}
void insert(int a, int i, int k) {
a = lower_bound(values, values + m, array<int, 2>{a, i}) - values;
update(a + 1, m - 1, k);
assign(a, k == 1 ? 0 : i);
}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
int n = a.size(), q = x.size();
for (int i = 0; i < n; ++i) {
values[i] = {a[i], i};
}
for (int i = 0; i < q; ++i) {
values[n + i] = {v[i], x[i]};
}
sort(values, values + n + q);
m = unique(values, values + n + q) - values;
for (int i = 0; i < n; ++i) {
insert(a[i], i, -1);
}
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
insert(a[x[i]], x[i], 1);
a[x[i]] = v[i];
insert(v[i], x[i], -1);
ans[i] = maxi[1];
}
return ans;
}
