#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT{
vector<int> vec;
int n;
void init(int _n){
n = _n;
vec.assign(n+1,0);
}
void add(int i, int v){
for(i++; i <= n; i+=i&-i)
vec[i] += v;
}
int get(int i){
int res = 0;
for(i++; i > 0; i-=i&-i)
res += vec[i];
return res;
}
void clear(){
fill(vec.begin(),vec.end(),0);
}
};
struct BIT2{
vector<int> vec;
int n;
void init(int _n){
n = _n;
vec.assign(n+1,0);
}
void add(int i, int v){
for(i++; i <= n; i+=i&-i)
vec[i] = max(vec[i],v);
}
int get(int i){
int res = 0;
for(i++; i > 0; i-=i&-i)
res = max(res,vec[i]);
return res;
}
void clear(){
fill(vec.begin(),vec.end(),0);
}
};
vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int N = (int) A.size();
int Q = (int) X.size();
vector<int> res(Q,0);
BIT bit; bit.init(N);
BIT2 bit2; bit2.init(N);
for(int t = 0; t < Q; t++){
A[X[t]] = V[t];
vector<pair<int,int>> vec(N);
for(int i = 0; i < N; i++)
vec[i] = {A[i],i};
sort(vec.begin(),vec.end());
for(int i = N-1; i >= 0; i--){
int j = vec[i].second;
int tmp = bit2.get(j);
bit.add(j,1);
vec[i].second -= bit.get(j-1);
tmp += vec[i].second != i;
bit2.add(j,tmp);
res[t] = max(res[t],tmp);
}
bit.clear();
bit2.clear();
}
return res;
}
