#include "bubblesort2.h"
#include "bits/stdc++.h"
using namespace std;
map<int,int> compress;
int n = 1;
struct segment_tree{
int t[1'000'001 * 3], lz[1'000'001 * 3];
void build(int l = 0, int r = n - 1, int k = 1){
if (l == r){
t[k] = 0;
lz[k] = 0;
return;
}
build(l,(l+r)/2,k*2);
build((l+r)/2+1,r,k*2+1);
t[k] = 0;
lz[k] = 0;
}
void push(int k, int l, int r){
t[k] += lz[k];
if (l != r){
lz[k * 2] += lz[k];
lz[k * 2 + 1] += lz[k];
}
lz[k] = 0;
}
void upd(int l, int r, int k, int L, int R, int V){
//cout << l << " " << r << " " << L << " " << R << " " << V << endl;
push(k,l,r);
if (l > R || r < L)return;
if (l >= L && r <= R){
lz[k] += V;
push(k,l,r);
return;
}
int mid = (l+r) / 2;
upd(l,mid,k*2,L,R,V);
upd(mid+1,r,k*2+1,L,R,V);
t[k] = max(t[k * 2], t[k * 2 + 1]);
}
int get(int W, int l = 0, int r = n - 1, int k = 1){
push(k,l,r);
if (l == r){
return t[k];
}
int mid = (l+r)/2;
if (W <= mid)return get(W,l,mid,k*2);
else return get(W,mid+1,r,k*2+1);
}
} st;
vector<int> countScans(vector<int> A, vector<int> X,vector<int> V){
int Q = X.size();
vector<int> answer(Q);
vector<vector<int>> AllElements;
for (int i = 0; i < (int)A.size(); i++)AllElements.push_back({A[i], i, 1});
for (int i = 0; i < (int)V.size(); i++)AllElements.push_back({V[i], i, 2});
sort(AllElements.begin(), AllElements.end());
vector<int>AI((int)A.size());
vector<int>VI((int)V.size());
for (int i = 0; i < (int)AllElements.size(); i++){
if (AllElements[i][2] == 2){
VI[AllElements[i][1]] = i;
}else{
AI[AllElements[i][1]] = i;
}
if (!i || AllElements[i][0] != AllElements[i - 1][0])compress[AllElements[i][0]] = i;
}
n = (int) AllElements.size();
st.build();
for (int i = 0; i < (int)A.size(); i++){
st.upd(0,n-1,1,compress[A[i]],n - 1, -1);
st.upd(0,n-1,1,AI[i], AI[i], i + 1);
//for (int j = 0; j < n; j++)cout << st.get(j) << ' ';
//cout << endl;
}
for (int i = 0; i < (int)X.size(); i++){
st.upd(0,n-1,1,compress[A[X[i]]], n - 1, 1);
st.upd(0,n-1,1,AI[X[i]], AI[X[i]], -X[i] - 1);
A[X[i]] = V[i];
AI[X[i]] = VI[i];
st.upd(0,n-1,1,compress[A[X[i]]],n - 1, -1);
st.upd(0,n-1,1,AI[X[i]], AI[X[i]], X[i] + 1);
//for (int j = 0; j < n; j++)cout << st.get(j) << ' ';
//cout << endl;
st.push(1,0,n-1);
answer[i] = st.t[1];
}
return answer;
}
