#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 {
vector <int> solve() {
return {};
}
}
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], 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)
sub3::solve();
return sub4::solve();
}
