#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
// #define F first
// #define S second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN = 1e6+5;
int n, q, seg[MXN<<2], lz[MXN<<2];
void Put(int x, int id) {
seg[id] += x;
lz[id] += x;
}
void Shift(int l, int r, int id) {
if (r - l > 1 && lz[id]) {
Put(lz[id], lc);
Put(lz[id], rc);
lz[id] = 0;
}
}
void Upd(int s, int e, int x, int l = 0, int r = MXN, int id=1) {
Shift(l, r, id);
if (s <= l && r <= e) {
Put(x, id);
return;
}
if (s < mid) Upd(s,e,x, l, mid, lc);
if (mid < e) Upd(s,e,x, mid, r, rc);
seg[id] = max(seg[lc], seg[rc]);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
q=X.size();
n = A.size();
vector<pii> vec;
for(int i=0;i<n;i++) {
vec.pb({A[i], i});
}
for(int j=0;j<q;j++) {
vec.pb({V[j], X[j]});
}
sort(vec.begin(), vec.end());
for (int i = 0; i < n; i++) {
int x = lower_bound(vec.begin(), vec.end(), make_pair(A[i], i)) - vec.begin();
Upd(x, x+1, i);
Upd(x+1, MXN, -1);
}
for (int i = 0; i < q; i++) {
int x = lower_bound(vec.begin(), vec.end(), make_pair(A[X[i]], X[i])) - vec.begin();
Upd(x, x+1, -X[i]);
Upd(x+1, MXN, 1);
A[X[i]] = V[i];
x = lower_bound(vec.begin(), vec.end(), make_pair(V[i], X[i])) - vec.begin();
Upd(x, x+1, X[i]);
Upd(x+1, MXN, -1);
X[i] = seg[1];
}
return X;
}
