#include "bubblesort2.h"
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int lazy[1 << 21], val[1 << 21];
void update(int Lf, int Rt, int x, int id, int l, int r) {
if (Lf <= l && r <= Rt) {
val[id] += x;
lazy[id] += x;
return;
}
int mid = l + r >> 1;
if (Lf <= mid) update(Lf, Rt, x, id << 1, l, mid);
if (Rt > mid) update(Lf, Rt, x, id << 1 | 1, mid + 1, r);
val[id] = max(val[id << 1], val[id << 1 | 1]) + lazy[id];
}
void update(int Lf, int Rt, int x) {
if (Lf <= Rt) {
update(Lf, Rt, x, 1, 0, 999999);
}
}
set<int> se[1000000];
std::vector<int> countScans(std::vector<int> a,std::vector<int> x,std::vector<int> v){
int N = a.size(), Q = x.size();
std::vector<int> answer(Q);
vector<int> comp;
for (int ai: a) {
comp.emplace_back(ai);
}
for (int vi: v) {
comp.emplace_back(vi);
}
sort(begin(comp), end(comp));
comp.resize(unique(begin(comp), end(comp)) - comp.begin());
int nnn = comp.size();
vector<int> cnt(nnn, 0);
for (int i = N - 1; i >= 0; i--) {
a[i] = lower_bound(begin(comp), end(comp), a[i]) - comp.begin();
if (!cnt[a[i]]) {
update(a[i], a[i], i + 1);
}
se[a[i]].insert(i + 1);
cnt[a[i]]++;
}
for (int p = 0; p < nnn; p++) {
if (cnt[p]) {
update(p, nnn - 1, -cnt[p]);
}
}
for (int &vi: v) {
vi = lower_bound(begin(comp), end(comp), vi) - comp.begin();
}
auto upd = [&] (int t, int p) {
int xnxx = a[p];
update(xnxx, nnn - 1, -t);
};
for (int i = 0; i < Q; i++) {
int p = x[i], xnxx = v[i];
upd(-1, p);
int vl = -*se[a[p]].rbegin();
se[a[p]].erase(p + 1);
if (se[a[p]].size()) {
vl += *se[a[p]].rbegin();
}
update(a[p], a[p], vl);
a[p] = xnxx;
upd(1, p);
vl = 0;
if (se[a[p]].size()) vl = -*se[a[p]].rbegin();
se[a[p]].insert(p + 1);
vl += *se[a[p]].rbegin();
update(a[p], a[p], vl);
answer[i] = val[1];
}
return answer;
}
////////////////////////////////////
