#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, MX = 1e9;
map<int, set<int>> pos;
struct lazyseg{
int seg[4 * N], lz[4 * N];
void push(int nd, int l, int r){
if(lz[nd] != 0){
seg[nd] += lz[nd];
if(l != r){
lz[nd * 2] += lz[nd];
lz[nd * 2 + 1] += lz[nd];
}
lz[nd] = 0;
}
}
void upd(int nd, int l, int r, int ql, int qr, int x){
push(nd, l, r);
if(qr < l || r < ql) return;
if(ql <= l && r <= qr){
lz[nd] += x;
push(nd, l, r);
return;
}
int md = (l + r) / 2;
upd(nd * 2, l, md, ql, qr, x);
upd(nd * 2 + 1, md + 1, r, ql, qr, x);
seg[nd] = max(seg[nd * 2], seg[nd * 2 + 1]);
}
int qry(int n){
push(1, 1, n);
return seg[1];
}
}s;
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
int n = A.size(), q = X.size();
vector<int> ans(q);
vector<int> comp = A;
for(auto x : V) comp.push_back(x);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
auto id = [&](int x){
return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
};
int m = comp.size();
for(int i = 0;i<n;i++){
pos[A[i]].insert(i);
s.upd(1, 1, m, id(A[i]), m, -1);
}
for(auto [el, ss] : pos){
s.upd(1, 1, m, id(el), id(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(1, 1, m, id(A[X[i]]), id(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(1, 1, m, id(V[i]), id(V[i]), *pos[V[i]].rbegin() - tv);
if(A[X[i]] < V[i]) s.upd(1, 1, m, id(A[X[i]]), id(V[i]) - 1, 1);
else if(V[i] < A[X[i]]) s.upd(1, 1, m, id(V[i]), id(A[X[i]]) - 1, -1);
A[X[i]] = V[i];
ans[i] = s.qry(m) + 1;
}
return ans;
}
