#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int N = 1e6 + 5;
struct node {
long long mx, lazy;
node(long long _mx = 0, long long _lazy = 0) {
mx = _mx;
lazy = _lazy;
}
node operator + (const node& o) const {
node res;
res.mx = max(mx, o.mx);
return res;
}
} it[N << 2];
void upd(int k, long long val) {
it[k].lazy += val;
it[k].mx += val;
}
void shift(int k) {
upd(k << 1, it[k].lazy);
upd(k << 1 | 1, it[k].lazy);
it[k].lazy = 0;
}
void update(int k, int l, int r, int u, int v, long long val) {
if(l > v || r < u) return;
if(u <= l && r <= v) {
upd(k, val);
return;
}
shift(k);
int mid = l + r >> 1;
update(k << 1, l, mid, u, v, val);
update(k << 1 | 1, mid + 1, r, u, v, val);
it[k] = it[k << 1] + it[k << 1 | 1];
}
set<int> s[N];
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
int n = a.size(), q = x.size();
vector<int> zip;
for(int val : a) zip.emplace_back(val);
for(int val : v) zip.emplace_back(val);
sort(zip.begin(), zip.end());
zip.resize(unique(zip.begin(), zip.end()) - zip.begin());
auto id = [&](int val) -> int {
return lower_bound(zip.begin(), zip.end(), val) - zip.begin() + 1;
};
int m = zip.size();
for(int i = 1; i <= m; ++i) {
s[i].insert(0);
}
for(int i = 0; i < n; ++i) {
int val = id(a[i]);
s[val].insert(i + 1);
update(1, 1, m, val, m, -1);
}
for(int i = 1; i <= m; ++i) update(1, 1, m, i, i, *s[i].rbegin());
vector<int> ans(q);
for(int i = 0; i < q; ++i) {
int v1 = id(a[x[i]]), v2 = id(v[i]);
int tmp = *s[v1].rbegin();
s[v1].erase(x[i] + 1);
update(1, 1, m, v1, v1, *s[v1].rbegin() - tmp);
tmp = *s[v2].rbegin();
s[v2].insert(x[i] + 1);
update(1, 1, m, v2, v2, *s[v2].rbegin() - tmp);
update(1, 1, m, v1, m, 1);
update(1, 1, m, v2, m, -1);
ans[i] = it[1].mx;
a[x[i]] = v[i];
}
return ans;
}
//int main() {
// file("A");
// auto ans = countScans({1, 2, 3, 4}, {0, 2}, {3, 1});
// for(int x : ans) cout << x << '\n';
//}
