#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
const int MX = 1e6 + 10;
struct segtree{
int st[MX << 2], lz[MX << 2];
void prop(int id, int l, int r){
if(lz[id] == 0) return;
st[id] += lz[id];
if(l != r){
lz[id << 1] += lz[id];
lz[id << 1|1] += lz[id];
}
lz[id] = 0;
}
void upd(int id, int from, int to, int l, int r, int v){
if(to < from) return;
// if(id == 1) cout << "update " << from << " to " << to << " value " << v << '\n';
prop(id, l, r);
if(r < from || l > to) return;
if(from <= l && r <= to){
lz[id] += v;
prop(id, l, r);
}else{
int mid = l + r >> 1;
upd(id << 1, from, to, l, mid, v);
upd(id << 1|1, from, to, mid + 1, r, v);
st[id] = max(st[id << 1], st[id << 1|1]);
}
}
int que(int id, int from, int to, int l, int r){
prop(id, l, r);
if(r < from || l > to) return 0;
if(from <= l && r <= to){
return st[id];
}else{
int mid = l + r >> 1;
return max(
que(id << 1, from, to, l, mid),
que(id << 1|1, from, to, mid + 1, r)
);
}
}
} S;
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
vector<pii> vec;
for(int i = 0; i < (int) A.size(); i++) vec.push_back({A[i], i});
for(int i = 0; i < (int) X.size(); i++) vec.push_back({V[i], X[i]});
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
int M = vec.size();
for(int i = 0; i < (int) A.size(); i++){
int idx = lower_bound(vec.begin(), vec.end(), make_pair(A[i], i)) - vec.begin();
S.upd(1, idx, idx, 0, M - 1, i);
S.upd(1, idx + 1, M - 1, 0, M - 1, -1);
}
vector<int> pos = A, ans;
for(int i = 0; i < (int) X.size(); i++){
int prev_idx = lower_bound(vec.begin(), vec.end(), make_pair(pos[X[i]], X[i])) - vec.begin();
int curr_idx = lower_bound(vec.begin(), vec.end(), make_pair(V[i], X[i])) - vec.begin();
S.upd(1, prev_idx, prev_idx, 0, M - 1, -X[i]);
S.upd(1, prev_idx + 1, M - 1, 0, M - 1, 1);
S.upd(1, curr_idx, curr_idx, 0, M - 1, X[i]);
S.upd(1, curr_idx + 1, M - 1, 0, M - 1, -1);
ans.push_back(S.que(1, 0, M - 1, 0, M - 1));
pos[X[i]] = V[i];
}
return ans;
}
