#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e6+5;
int n, q, t;
vector<int> res;
map<pair<int, int>, int> mp;
struct segtree
{
int d[4*nx], lz[4*nx];
void pushlz(int l, int r, int i)
{
d[i]+=lz[i];
if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
lz[i]=0;
}
void update(int l, int r, int i, int ql, int qr, int vl)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l ,r, i), void();
int md=(l+r)/2;
update(l, md, 2*i, ql, qr, vl);
update(md+1, r, 2*i+1, ql, qr, vl);
d[i]=max(d[2*i], d[2*i+1]);
}
} s;
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
n=A.size();
q=X.size();
for (int i=0; i<n; i++) mp[{A[i], i}]=0;
for (int i=0; i<q; i++) mp[{V[i], X[i]}]=0;
for (auto &[x, y]:mp) y=++t;
for (int i=0; i<n; i++) s.update(1, n+q, 1, mp[{A[i], i}], mp[{A[i], i}], i), s.update(1, n+q, 1, mp[{A[i], i}], n+q, -1);
for (int i=0; i<q; i++)
{
s.update(1, n+q, 1, mp[{A[X[i]], X[i]}], mp[{A[X[i]], X[i]}], -X[i]);
s.update(1, n+q, 1, mp[{A[X[i]], X[i]}], n+q, 1);
A[X[i]]=V[i];
s.update(1, n+q, 1, mp[{A[X[i]], X[i]}], mp[{A[X[i]], X[i]}], X[i]);
s.update(1, n+q, 1, mp[{A[X[i]], X[i]}], n+q, -1);
res.push_back(s.d[1]+1);
}
return res;
}
