#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, K = 1e6 + 6;
const int INF = 1e9 + 1;
typedef pair<int, int> pii;
struct BIT{
int bit[K + 1];
void init(int n){
for(int i = 1; i <= n; i++){
bit[i] = 0;
}
}
void upd(int p, int v){
while(p <= K){
bit[p] += v;
p += p & -p;
}
}
int qry(int p){
int ret = 0;
while(p){
ret += bit[p];
p -= p & -p;
}
return ret;
}
} bit;
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
int n = A.size(), q = X.size();
vector<int> ans(q);
set<pair<int, int>> S; map<pii, int> M;
for(int i = 0; i < n; i++) S.insert({A[i], i});
for(int i = 0; i < q; i++) S.insert({V[i], X[i]});
{ int idx = 0; for(auto i : S) M[i] = ++idx; }
int k = S.size();
for(int i = 0; i < n; i++) A[i] = M[{A[i], i}];
for(int i = 0; i < q; i++) V[i] = M[{V[i], X[i]}];
for(int i = 0; i < q; i++){
A[X[i]] = V[i];
bit.init(k);
int a = 0;
for(int j = 0; j < n; j++){
a = max(a, j - bit.qry(A[j]));
bit.upd(A[j], 1);
}
ans[i] = a;
}
return ans;
}
