#include "bubblesort2.h"
#include <bits/stdc++.h>
#define N 1000050
#define l (2*nod)
#define r (2*nod + 1)
#define mid ((a + b)/2)
using namespace std;
typedef long long ll;
int inf = 2000000000;
int n, v[N], c, bit[N], lim;
vector<int> val;
map<int, int> mapa;
set<int> pos[N];
struct T
{
int tree[4*N], lazy[4*N];
inline void init()
{
for(int i = 0; i < 4*N; i++) lazy[i] = tree[i] = 0;
}
inline void prop(int nod, int a, int b)
{
if(!lazy[nod]) return;
tree[nod] += lazy[nod];
if(a != b)
{
lazy[l] += lazy[nod];
lazy[r] += lazy[nod];
}
lazy[nod] = 0;
return;
}
void upd(int nod, int a, int b, int i, int j, int x)
{
prop(nod, a, b);
if(j < a or i > b) return;
if(i <= a and j >= b)
{
tree[nod] += x;
if(a != b)
{
lazy[l] += x;
lazy[r] += x;
}
return;
}
upd(l, a, mid, i, j, x), upd(r, mid + 1, b, i, j, x);
tree[nod] = max(tree[l], tree[r]);
}
int query(int nod, int a, int b, int i, int j)
{
prop(nod, a, b);
if(j < a or i > b) return -inf;
if(i <= a and j >= b) return tree[nod];
return max(query(l, a, mid, i, j), query(r, mid + 1, b, i, j));
}
} Tree;
inline void remove(int x, int po)
{
Tree.upd(1, 1, lim, x, lim, 1);
int p = -(*pos[x].begin());
pos[x].erase(-po);
if(p == po)
{
int pp = -(*pos[x].begin());
Tree.upd(1, 1, lim, x, x, pp - p);
}
}
inline void add(int x, int po)
{
Tree.upd(1, 1, lim, x, lim, -1);
int p = -(*pos[x].begin());
if(po > p)
{
Tree.upd(1, 1, lim, x, x, po - p);
}
pos[x].insert(-po);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int Q = X.size();
n = A.size();
for(auto x: A) val.push_back(x);
for(auto x: V) val.push_back(x);
sort(val.begin(), val.end());
for(auto x: val) if(!mapa[x]) mapa[x] = ++c;
for(int i = 0; i < N; i ++) pos[i].insert(10000);
for(int i = 0; i < n; i++) v[i] = mapa[A[i]];
for(int i = 0; i < Q; i++) V[i] = mapa[V[i]];
for(int i = 0; i < n; i++) pos[v[i]].insert(-i);
vector<int> answer(Q);
Tree.init();
lim = N - 1;
for(int i = 0, soma = 0; i < N; i++)
{
soma += pos[i].size() - 1;
if(pos[i].empty()) continue;
int x = -(*pos[i].begin());
Tree.upd(1, 1, lim, i, i, x - soma);
}
for(int j = 0; j < Q; j++)
{
int x = X[j], val = v[X[j]], novo = V[j];
remove(val, x);
add(novo, x);
v[x] = novo;
answer[j] = 1 + Tree.query(1, 1, lim, 1, lim);
}
return answer;
}
