#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000500;
int G;
int a[maxn];
int t[4 * maxn];
int lz[4 * maxn];
void push(int x)
{
lz[x + x] += lz[x];
lz[x + x + 1] += lz[x];
t[x + x] += lz[x];
t[x + x + 1] += lz[x];
lz[x] = 0;
}
void upd(int x, int l, int r, int p, int val)
{
if(l == r){
t[x] += val;
return;
}
push(x);
int m = (l + r) / 2;
if(p <= m)upd(x + x, l, m, p, val);
else upd(x + x + 1, m + 1, r, p, val);
t[x] = max(t[x + x], t[x + x + 1]);
}
void upd(int x, int l, int r, int tl, int tr, int val)
{
if(tl > tr)return;
if(l == tl && r == tr){
t[x] += val;
lz[x] += val;
return;
}
int m = (l + r) / 2;
push(x);
upd(x + x, l, m, tl, min(tr, m), val);
upd(x + x + 1, m + 1, r, max(tl, m + 1), tr, val);
t[x] = max(t[x + x], t[x + x + 1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
int Q=X.size();
vector<int> answer;
int n = (int)A.size();
vector<pair<int, int>> g;
for(int i = 0; i < Q; i++){
g.push_back({V[i], -(i + 1)});
}
for(int i = 0; i < n; i++){
g.push_back({A[i], i});
}
map<int, int> m;
sort(g.begin(), g.end());
for(int i = 0; i < (int)g.size(); i++){
if(g[i].second >= 0){
A[g[i].second] = ++G;
}else{
V[-g[i].second - 1] = ++G;
}
}
for(int i = 0; i < n; i++){
upd(1, 1, G, A[i], G, -1);
upd(1, 1, G, A[i], i + 1);
}
for(int i = 0; i < Q; i++){
upd(1, 1, G, A[X[i]], -(X[i] + 1));
upd(1, 1, G, A[X[i]], G, 1);
A[X[i]] = V[i];
upd(1, 1, G, A[X[i]], (X[i] + 1));
upd(1, 1, G, A[X[i]], G, -1);
answer.push_back(t[1]);
}
return answer;
}
