#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int st[4 * maxn], lazy[4 * maxn];
void apply(int id, int val){
st[id] += val, lazy[id] += val;
}
void update(int id, int l, int r, int u, int v, int val){
if(v < u || r < u || v < l) return;
if(u <= l && r <= v) apply(id, val);
else{
apply(id * 2, lazy[id]);
apply(id * 2 + 1, lazy[id]);
lazy[id] = 0;
int mid = (l + r) / 2;
update(id * 2, l, mid, u, v, val);
update(id * 2 + 1, mid + 1, r, u, v, val);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){
vector<pair<int, int>> cmp;
for(int i = 0; i < a.size(); i++) cmp.push_back({a[i], i});
for(int i = 0; i < v.size(); i++) cmp.push_back({v[i], x[i]});
sort(cmp.begin(), cmp.end());
cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
int n = cmp.size();
for(int i = 0; i < a.size(); i++){
a[i] = lower_bound(cmp.begin(), cmp.end(), pair<int, int>{a[i], i}) - cmp.begin() + 1;
update(1, 1, n, a[i], a[i], i);
update(1, 1, n, a[i] + 1, n, -1);
}
vector<int> res;
for(int i = 0; i < v.size(); i++){
v[i] = lower_bound(cmp.begin(), cmp.end(), pair<int, int>{v[i], x[i]}) - cmp.begin() + 1;
update(1, 1, n, a[x[i]], a[x[i]], -x[i]);
update(1, 1, n, a[x[i]] + 1, n, 1);
update(1, 1, n, v[i], v[i], x[i]);
update(1, 1, n, v[i] + 1, n, -1);
a[x[i]] = v[i];
res.push_back(st[1]);
}
return res;
}
