#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
const int base = 1<<20;
int tree[base<<1];
void update(int v, int x){
v += base;
tree[v] += x;
v /= 2;
while(v){
tree[v] = tree[2*v] + tree[2*v+1];
v /= 2;
}
}
int query(int a, int b){
a += base - 1;
b += base + 1;
int res = 0;
while(a/2 != b/2){
if(a % 2 == 0) res += tree[a+1];
if(b % 2 == 1) res += tree[b-1];
a/=2;
b/=2;
}
return res;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
int n = A.size();
int Q = X.size();
vector<int> res(Q);
map<long long, int> skalowanie;
for(auto i : A){
skalowanie[i] = 0;
}
for(auto i : V){
skalowanie[i] = 0;
}
int id = 0;
for(auto &i : skalowanie) i.second = ++id;
for(auto i : A) update(skalowanie[i], 1);
for(int i = 0; i < Q; ++i){
update(skalowanie[A[X[i]]], -1);
A[X[i]] = V[i];
update(skalowanie[A[X[i]]], 1);
int curRes = 0;
for(int j = 0; j < n; ++j){
// cerr << j << ": " << query(skalowanie[i]+1, id) << "\n";
curRes = max(curRes, query(skalowanie[A[j]]+1, id) - (n - j - 1));
}
res[i] = curRes;
}
return res;
}
