#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif
// #define int long long
const int maxn = 1e6 + 5;
struct SegmentTree{
int n;
vector<int> a, lazy;
SegmentTree(int _n){
n = _n;
a.resize(n * 4 + 4); lazy.resize(n * 4 + 4);
}
void update_node(int i, int v){
a[i] += v;
lazy[i] += v;
}
void down(int id){
update_node(id * 2, lazy[id]); update_node(id * 2 + 1, lazy[id]);
lazy[id] = 0;
}
void update(int u, int v, int val){if (u <= v) update(u, v, val, 0, n-1, 1);}
void update(int u, int v, int val, int l, int r, int id){
if (u <= l && r <= v){
update_node(id, val);
return;
}
if (lazy[id]) down(id);
int mid = (l + r) >> 1;
if (u <= mid) update(u, v, val, l, mid, id * 2);
if (v > mid) update(u, v, val, mid + 1, r, id * 2 + 1);
a[id] = max(a[id * 2], a[id * 2 + 1]);
}
int get(){return a[1];}
};
set<int> pos[maxn];
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
int n = a.size();
int q = v.size();
for (auto& x : a) cin >> x;
for (auto& u : x) cin >> u;
for (auto& x : v) cin >> x;
debug(a, x, v);
vector<int> b = a;
for (auto x : v) b.push_back(x);
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (auto& x : a) x = lower_bound(b.begin(), b.end(), x) - b.begin();
for (auto& x : v) x = lower_bound(b.begin(), b.end(), x) - b.begin();
int m = b.size();
for (int i = 0; i < n; i++){
pos[a[i]].insert(i);
}
SegmentTree seg(m);
for (int i = 0; i < m; i++){
pos[i].insert(-1e9);
seg.update(i, i, *pos[i].rbegin());
seg.update(i, m - 1, -(pos[i].size() - 1));
}
vector<int> ans(q);
debug(ans);
for (int i = 0; i < q; i++){
int idx = x[i], val = v[i];
seg.update(a[idx], m - 1, 1);
seg.update(a[idx], a[idx], -*pos[a[idx]].rbegin());
pos[a[idx]].erase(idx);
seg.update(a[idx], a[idx], *pos[a[idx]].rbegin());
a[idx] = val;
seg.update(a[idx], m - 1, -1);
seg.update(a[idx], a[idx], -*pos[a[idx]].rbegin());
pos[a[idx]].insert(idx);
seg.update(a[idx], a[idx], *pos[a[idx]].rbegin());
ans[i] = seg.get() + 1;
debug(a);
}
return ans;
}
