#include "bubblesort2.h"
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
#define ll long long
const int MX = 500005;
const ll inf = 696969696969ll;
ll st[MX * 4], lz[MX * 4];
void prop(int nd, int cl, int cr){
if(lz[nd]){
st[nd] += lz[nd];
if(cl != cr)
lz[nd * 2] += lz[nd],
lz[nd * 2 + 1] += lz[nd];
lz[nd] = 0;
}
}
void upd(int nd, int cl, int cr, int lf, int rg, ll val){
prop(nd, cl, cr);
if(rg < cl || cr < lf || lf > rg || cl > cr) return;
if(lf <= cl && cr <= rg){
lz[nd] += val;
prop(nd, cl, cr);
return;
}
upd(nd * 2, cl, (cl + cr) / 2, lf, rg, val);
upd(nd * 2 + 1, (cl + cr) / 2 + 1, cr, lf, rg, val);
st[nd] = max(st[nd * 2], st[nd * 2 + 1]);
}
int que(int nd, int cl, int cr, int lf, int rg){
prop(nd, cl, cr);
if(cl > cr || lf > rg || rg < cl || cr < lf) return 0;
if(lf <= cl && cr <= rg) return st[nd];
return max(
que(nd * 2, cl, (cl + cr) / 2, lf, rg),
que(nd * 2 + 1, (cl + cr) / 2 + 1, cr, lf, rg)
);
}
vector<pair<int, int> > cc;
void ins(int ps, int val){
int i = lower_bound(cc.begin(), cc.end(), make_pair(val, ps)) - cc.begin();
upd(1, 0, cc.size() - 1, i, i, inf + ps);
upd(1, 0, cc.size() - 1, i + 1, cc.size() - 1, -1);
}
void del(int ps, int val){
int i = lower_bound(cc.begin(), cc.end(), make_pair(val, ps)) - cc.begin();
upd(1, 0, cc.size() - 1, i, i, -(inf + ps));
upd(1, 0, cc.size() - 1, i + 1, cc.size() - 1, 1);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
for(int i = 0; i < A.size(); i ++)
cc.push_back({A[i], i});
sort(cc.begin(), cc.end());
for(int i = 0; i < X.size(); i ++)
cc.push_back({V[i], X[i]});
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
upd(1, 0, cc.size() - 1, 0, cc.size() - 1, -inf);
for(int i = 0; i < A.size(); i ++)
ins(i, A[i]);
vector<int> ans;
for(int i = 0; i < X.size(); i ++){
del(X[i], A[X[i]]);
A[X[i]] = V[i];
ins(X[i], A[X[i]]);
ans.push_back(que(1, 0, cc.size() - 1, 0, cc.size() - 1));
}
return ans;
}
