#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
template <class T> bool minimize(T &a, T b) {
if (a > b) return a = b, true;
return false;
}
template <class T> bool maximize(T &a, T b) {
if (a < b) return a = b, true;
return false;
}
const int N = 5e5 + 2;
int n, q;
int a[N], x[N], v[N];
namespace sub2 {
vector <int> solve() {
vector <int> res;
for (int _ = 0; _ < q; _++) {
a[x[_]] = v[_];
vector <int> b(a, a + n + 1);
sort (b.begin() + 1, b.end());
int ans = 0;
for (int i = 1; i <= n; i++) {
int k = upper_bound(b.begin() + 1, b.end(), a[i]) - b.begin() - 1;
maximize(ans, i - k);
}
res.emplace_back(ans);
}
return res;
}
}
namespace sub3 {
set <int> pos[102];
vector <int> solve() {
for (int i = 1; i <= 100; i++) pos[i].clear();
for (int i = 1; i <= n; i++) pos[a[i]].emplace(i);
vector <int> res;
for (int _ = 0; _ < q; _++) {
pos[a[x[_]]].erase(x[_]);
a[x[_]] = v[_];
pos[a[x[_]]].emplace(x[_]);
int ans = 0, cnt = 0;
for (int i = 1; i <= 100; i++) if (!pos[i].empty()) {
cnt += pos[i].size();
maximize(ans, *pos[i].rbegin() - cnt);
}
res.emplace_back(ans);
}
return res;
}
}
namespace sub4 {
struct SegmentTree {
vector <int> st, lazy;
SegmentTree () {}
SegmentTree (int len) {
st.assign(len * 4 + 1, 0);
lazy.assign(len * 4 + 1, 0);
}
void push_down(int id) {
int k = lazy[id]; lazy[id] = 0;
st[id << 1] += k; lazy[id << 1] += k;
st[id << 1 | 1] += k; lazy[id << 1 | 1] += k;
}
void update(int id, int l, int r, int u, int v, int val) {
if (u > r || v < l) return;
if (u <= l && r <= v) {
st[id] += val;
lazy[id] += val;
return;
}
int mid = (l + r) >> 1; push_down(id);
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int getMax(int l, int r) {
return st[1];
}
} ST;
set <int> pos[N << 1];
int sz;
void add(int val, int p) {
int maP = (pos[val].empty() ? 0 : *pos[val].rbegin());
pos[val].emplace(p);
if (maP < p) ST.update(1, 1, sz, val, val, p - maP);
ST.update(1, 1, sz, val, sz, -1);
}
void remove(int val, int p) {
int maP = *pos[val].rbegin();
pos[val].erase(p);
if (pos[val].empty() || maP == p) {
int ma2 = (pos[val].empty() ? 0 : *pos[val].rbegin());
ST.update(1, 1, sz, val, val, ma2 - maP);
}
ST.update(1, 1, sz, val, sz, +1);
}
vector <int> solve() {
vector <int> cmp;
for (int i = 1; i <= n; i++) cmp.emplace_back(a[i]);
for (int i = 0; i < q; i++) cmp.emplace_back(v[i]);
sort (cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
for (int i = 1; i <= n; i++)
a[i] = upper_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin();
for (int i = 0; i < q; i++)
v[i] = upper_bound(cmp.begin(), cmp.end(), v[i]) - cmp.begin();
sz = cmp.size();
ST = SegmentTree(sz);
for (int i = 1; i <= sz; i++) pos[i].clear();
vector <int> res;
for (int i = 1; i <= n; i++) add(a[i], i);
for (int i = 0; i < q; i++) {
remove(a[x[i]], x[i]);
a[x[i]] = v[i];
add(a[x[i]], x[i]);
res.emplace_back(ST.getMax(1, sz));
}
return res;
}
}
vector <int> countScans(vector <int> A,vector <int> X, vector <int> V){
n = A.size(); q = X.size();
for (int i = 1; i <= n; i++) a[i] = A[i - 1];
for (int i = 0; i < q; i++) x[i] = X[i] + 1, v[i] = V[i];
if (max(A.size(), X.size()) <= 8e3) return sub2::solve();
if (max(*max_element(A.begin(), A.end()), *max_element(V.begin(), V.end())) <= 100)
return sub3::solve();
return sub4::solve();
}
