#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf = 1e9;
struct ST{
vector<int> t, p;
int n;
ST(int ns){
n = ns;
t.resize(4 * n);
p.resize(4 * n);
}
void push(int v){
if (!p[v]) return;
int vv = 2 * v;
t[vv] += p[v]; t[vv + 1] += p[v];
p[vv] += p[v]; p[vv + 1] += p[v];
p[v] = 0;
}
void add(int v, int tl, int tr, int& l, int& r, int& x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
p[v] += x;
t[v] += x;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v);
add(vv, tl, tm, l, r, x);
add(vv + 1, tm + 1, tr, l, r, x);
t[v] = max(t[vv], t[vv + 1]);
}
void add(int l, int r, int x){
add(1, 1, n, l, r, x);
}
int get(){
return t[1];
}
};
vector<int> countScans(vector<int> a, vector<int> p, vector<int> x){
a.insert(a.begin(), 0);
p.insert(p.begin(), 0);
x.insert(x.begin(), 0);
int n = (int) a.size() - 1;
vector<int> all = {0};
for (int i = 1; i <= n; i++) all.pb(a[i]);
int q = (int) p.size() - 1;
for (int i = 1; i <= q; i++) p[i]++;
for (int i = 1; i <= q; i++) all.pb(x[i]);
sort(all.begin(), all.end());
vector<int> :: iterator it;
vector<int> y(n + 1);
map<int, int> mp;
for (int i = 1; i < all.size(); i++){
if (all[i] != all[i - 1]){
mp[all[i]] = i;
}
}
int m = (int) all.size() - 1;
ST T(m);
T.add(1, m, -inf);
auto rem = [&](int x){
it = lower_bound(all.begin(), all.end(), all[x]);
int j = (int) (it - all.begin());
T.add(1, j - 1, -1);
T.add(x, x, -inf);
};
auto add = [&](int x, int i){
it = lower_bound(all.begin(), all.end(), all[x]);
int j = (int) (it - all.begin());
T.add(1, j - 1, 1);
T.add(x, x, inf + i);
};
for (int i = 1; i <= n; i++){
y[i] = mp[a[i]]++;
add(y[i], i);
}
vector<int> out;
for (int i = 1; i <= q; i++){
rem(y[p[i]]);
y[p[i]] = mp[x[i]]++;
add(y[p[i]], p[i]);
out.pb(T.get() - n);
}
return out;
}
