#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define all(a) begin(a), end(a)
#define csz(a) (int) a.size()
#define fori(i, a, b) for(int i = (int) a; i <= (int) b; ++i)
#define rofi(i, b, a) for(int i = (int) b; i >= (int) a; --i)
#define foreach(tt, a) for(auto &tt: a)
#define long long long
const int INF = 1e9+1;
const long MOD = 1e9+7, LINF = 1e16+1;
mt19937 eng;
uniform_int_distribution<> uintd;
struct node {
node *l, *r;
pair<int,int> key;
int prior, cnt;
int val, agg, lz;
node(pair<int,int> key, int val): key(key), val(val) {
l = NULL, r = NULL;
prior = uintd(eng), cnt = 1;
agg = val;
lz = 0;
}
};
using pnode = node*;
void apply(pnode t) {
if(!t || t->lz == 0) return;
t->agg += t->lz;
t->val += t->lz;
if(t->l) t->l->lz += t->lz;
if(t->r) t->r->lz += t->lz;
t->lz = 0;
}
void update(pnode t) {
if(!t) return;
apply(t->l), apply(t->r);
t->cnt = 1;
t->agg = t->val;
if(t->l) t->agg = max(t->l->agg, t->agg), t->cnt += t->l->cnt;
if(t->r) t->agg = max(t->r->agg, t->agg), t->cnt += t->r->cnt;
}
void split(pnode t, pnode &l, pnode &r, pair<int,int> targ) {
apply(t);
if(!t) return void(l = r = NULL);
if(targ < t->key) split(t->l, l, t->l, targ), r = t; // equal goes left
else split(t->r, t->r, r, targ), l = t;
update(t);
}
void merge(pnode& t, pnode l, pnode r) {
apply(l), apply(r);
if(!l || !r) return void(t = (l ? l : r));
if(l->prior > r->prior) merge(l->r, l->r, r), t = l;
else merge(r->l, l, r->l), t = r;
update(t);
}
void insert(pnode& t, pair<int,int> key, int val) {
pnode lf, rg;
split(t, lf, rg, key);
merge(t, lf, new node(key, val));
merge(t, t, rg);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
eng = mt19937(0);
pnode root = NULL;
vector<pair<int,int> > B;
fori(i, 0, csz(A)-1) B.epb(A[i], i);
sort(all(B));
fori(i, 0, csz(B)-1) {
insert(root, B[i], B[i].second - i);
}
vector<int> res(csz(X));
fori(i, 0, csz(X)-1) {
auto val1 = mp(A[X[i]], X[i]);
auto val1_less = mp(A[X[i]], X[i]-1);
auto val2 = mp(V[i], X[i]);
pnode p1, p2, p3;
split(root, p2, p3, val1);
split(p2, p1, p2, val1_less);
if(p3) ++p3->lz;
merge(root, p1, p3);
delete p2;
split(root, p1, p2, val2);
if(p2) --p2->lz;
insert(p1, val2, val2.second - (p1 ? p1->cnt : 0));
merge(root, p1, p2);
A[X[i]] = V[i];
res[i] = root->agg;
}
return res;
}
