#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, MX = 1e9;
map<int, set<int>> pos;
set<int> el;
struct lazysparseseg{
struct node{
int v, lz;
node *l, *r;
node(int v):v(v), lz(0), l(0), r(0){}
};
typedef node* pnode;
pnode rt = 0;
void push(pnode &k, int l, int r){
if(!k) return;
if(k->lz != 0){
k->v += k->lz;
if(l != r){
if(!k->l) k->l = new node(0);
k->l->lz += k->lz;
if(!k->r) k->r = new node(0);
k->r->lz += k->lz;
}
k->lz = 0;
}
}
void upd(pnode &k, int l, int r, int ql, int qr, int x){
if(qr < l || r < ql) return;
if(!k) k = new node(0);
push(k, l, r);
if(ql <= l && r <= qr){
k->lz += x;
push(k, l, r);
return;
}
int md = (l + r) / 2;
upd(k->l, l, md, ql, qr, x);
upd(k->r, md + 1, r, ql, qr, x);
if(k->l) push(k->l, l, md);
if(k->r) push(k->r, md + 1, r);
k->v = max(k->l ? k->l->v : 0, k->r ? k->r->v : 0);
}
int qry(pnode k, int l, int r, int ql, int qr){
push(k, l, r);
if(!k || qr < l || r < ql) return 0;
if(ql <= l && r <= qr) return k->v;
int md = (l + r) / 2;
return max(qry(k->l, l, md, ql, qr), qry(k->r, md + 1, r, ql, qr));
}
}s;
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
int n = A.size(), q = X.size();
vector<int> ans(q);
for(int i = 0;i<n;i++){
pos[A[i]].insert(i);
s.upd(s.rt, 1, MX, A[i], MX, -1);
}
for(auto [el, ss] : pos){
s.upd(s.rt, 1, MX, el, el, *ss.rbegin());
}
for(int i = 0;i<q;i++){
int tb = *pos[A[X[i]]].rbegin();
pos[A[X[i]]].erase(X[i]);
int nw;
if(pos[A[X[i]]].empty()) nw = 0;
else nw = *pos[A[X[i]]].rbegin();
s.upd(s.rt, 1, MX, A[X[i]], A[X[i]], nw - tb);
int tv;
if(pos[V[i]].empty()) tv = 0;
else tv = *pos[V[i]].rbegin();
pos[V[i]].insert(X[i]);
s.upd(s.rt, 1, MX, V[i], V[i], *pos[V[i]].rbegin() - tv);
if(A[X[i]] < V[i]) s.upd(s.rt, 1, MX, A[X[i]], V[i] - 1, 1);
else if(V[i] < A[X[i]]) s.upd(s.rt, 1, MX, V[i], A[X[i]] - 1, -1);
A[X[i]] = V[i];
ans[i] = s.qry(s.rt, 1, MX, 1, MX) + 1;
}
return ans;
}
