#include "bubblesort2.h"
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int inf = int(1E9);
#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
struct segtree {
int n;
std::vector<std::set<int>> ids;
std::vector<int> tree, cnt;
segtree(int n_) : n(n_), ids(n), tree(n << 1), cnt(n << 1) {}
void pull(int v, int l, int r) {
def;
tree[v] = std::max(tree[lv], tree[rv] - cnt[lv]);
cnt[v] = cnt[lv] + cnt[rv];
}
void modify(int v, int l, int r, int p, int x, int c) {
debug(v, l, r, p, x, c);
if (l == r) {
cnt[v] = c;
tree[v] = x - c + 1;
return;
}
def;
if (p <= mid) {
modify(lv, l, mid, p, x, c);
} else {
modify(rv, mid + 1, r, p, x, c);
}
debug(1);
pull(v, l, r);
}
void modify(int p, int x, int c) {
modify(0, 0, n - 1, p, x, c);
}
void insert(int p, int x) {
ids[p].emplace(x);
modify(p, *ids[p].rbegin(), ids[p].size());
}
void erase(int p, int x) {
ids[p].erase(x);
modify(p, ids[p].empty() ? -inf : *ids[p].begin(), ids[p].size());
}
};
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
std::vector<int> ids(A.begin(), A.end());
ids.insert(ids.end(), V.begin(), V.end());
std::sort(ids.begin(), ids.end());
int n;
ids.resize(n = int(std::unique(ids.begin(), ids.end()) - ids.begin()));
segtree seg(n);
int N = int(A.size());
int Q = int(X.size());
debug(1);
for (int i = 0; i < N; ++i) {
A[i] = int(std::lower_bound(ids.begin(), ids.end(), A[i]) - ids.begin());
seg.insert(A[i], i);
}
for (int i = 0; i < Q; ++i) {
V[i] = int(std::lower_bound(ids.begin(), ids.end(), V[i]) - ids.begin());
}
debug(2);
std::vector<int> ans(Q);
for (int i = 0; i < Q; ++i) {
seg.erase(A[X[i]], X[i]);
A[X[i]] = V[i];
seg.insert(A[X[i]], X[i]);
ans[i] = seg.tree[0];
}
return ans;
}
