#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 7;
const int NAX = (int) 1e6 + 7;
int N;
int coef[NAX];
int value[NAX];
bool valid[NAX];
void add(int l, int r, int x) {
for (int j = l; j <= r; j++) {
value[j] += x;
}
}
int getMax() {
int sol = 0;
for (int i = 1; i <= N; i++) {
sol = max(sol, value[i]);
}
return sol;
}
vector<int> innterCountScans(vector<ll> a, vector<int> pos, vector<ll> ChangeValue) {
int n = (int) a.size();
int q = (int) pos.size();
for (int i = 0; i < n; i++) {
a[i] = a[i] * (ll) (n + 1) + i;
}
for (int it = 0; it < q; it++) {
ChangeValue[it] = ChangeValue[it] * (ll) (n + 1) + pos[it];
}
map<ll, int> mp;
for (auto &x : a) {
mp[x] = 0;
}
for (auto &x : ChangeValue) {
mp[x] = 0;
}
{
int ij = 0;
for (auto &it : mp) {
it.second = ++ij;
}
N = ij;
assert(N <= n + q);
}
for (auto &x : a) {
x = mp[x];
}
for (auto &x : ChangeValue) {
x = mp[x];
}
for (int i = 1; i <= N; i++) {
coef[i] = -INF;
}
add(1, N, -INF);
for (int i = 0; i < n; i++) {
valid[a[i]] = 1;
add(a[i], a[i], i - coef[a[i]]);
coef[a[i]] += i - coef[a[i]];
add(a[i], N, -1);
}
vector<int> sol;
for (int it = 0; it < q; it++) {
if (1) {
valid[a[pos[it]]] = 0;
add(a[pos[it]], N, +1);
add(a[pos[it]], a[pos[it]], -(coef[a[pos[it]]] + INF));
coef[a[pos[it]]] += -(coef[a[pos[it]]] + INF);
a[pos[it]] = ChangeValue[it];
valid[a[pos[it]]] = 1;
add(a[pos[it]], N, -1);
add(a[pos[it]], a[pos[it]], pos[it] - coef[a[pos[it]]]);
coef[a[pos[it]]] += pos[it] - coef[a[pos[it]]];
}
sol.push_back(getMax() + 1);
}
return sol;
}
vector<int> countScans(vector<int> a, vector<int> b, vector<int> c) {
vector<ll> X, Z;
for (auto &it : a) {
X.push_back(it);
}
for (auto &it : c) {
Z.push_back(it);
}
return innterCountScans(X, b, Z);
}
