#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)5e5 + 10;
const int M = N * 2;
const int inf = (int)1e9;
struct Node{
int maxi;
int cnt;
int lzy;
};
vector<pii> cmp;
Node T[M * 4 + 512];
void push(int node, int cl, int cr){
T[node].maxi -= T[node].lzy;
T[node].cnt += T[node].lzy;
if(cl != cr){
T[node * 2].lzy += T[node].lzy;
T[node * 2 + 1].lzy += T[node].lzy;
}
T[node].lzy = 0;
}
void set_val(int node, int cl, int cr, int id, int v){
push(node, cl, cr);
if(cl > id || cr < id) return;
if(cl == cr){
T[node].maxi = v;
return;
}
int mid = (cl + cr) / 2;
set_val(node * 2, cl, mid, id, v);
set_val(node * 2 + 1, mid + 1, cr, id, v);
T[node].maxi = max(T[node * 2].maxi, T[node * 2 + 1].maxi);
}
void incr(int node, int cl, int cr, int tl, int tr, int v){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
T[node].lzy = v;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
incr(node * 2, cl, mid, tl, tr, v);
incr(node * 2 + 1, mid + 1, cr, tl, tr, v);
T[node].maxi = max(T[node * 2].maxi, T[node * 2 + 1].maxi);
}
int get(int node, int cl, int cr, int tl, int tr){
push(node, cl, cr);
if(cr < tl) return 0;
if(cl > tr) return 0;
if(cl >= tl && cr <= tr){
return T[node].cnt;
}
int mid = (cl + cr) / 2;
return get(node * 2, cl, mid, tl, tr) + get(node * 2 + 1, mid + 1, cr, tl, tr);
}
void build(int node, int cl, int cr){
T[node].maxi = -inf;
if(cl == cr){
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
vector<int> outp;
int n = A.size();
int q = X.size();
int sol;
for(int i = 0 ; i < n; i ++ ){
cmp.push_back(mp(A[i], i));
}
for(int iq = 0; iq < q; iq ++ ){
cmp.push_back(mp(V[iq], X[iq]));
}
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
int m = cmp.size();
build(1, 0, m - 1);
int idx;
for(int i = 0 ; i < n; i ++ ){
idx = lower_bound(cmp.begin(), cmp.end(), mp(A[i], i)) - cmp.begin();
incr(1, 0, m - 1, idx + 1, m - 1, +1);
}
int vv;
for(int i = 0 ; i < n; i ++ ){
idx = lower_bound(cmp.begin(), cmp.end(), mp(A[i], i)) - cmp.begin();
vv = get(1, 0, m - 1, idx, idx);
set_val(1, 0, m - 1, idx, i - vv);
}
for(int iq = 0; iq < q; iq ++ ){
idx = lower_bound(cmp.begin(), cmp.end(), mp(A[X[iq]], X[iq])) - cmp.begin();
vv = get(1, 0, m - 1, idx, idx);
set_val(1, 0, m - 1, idx, -inf);
incr(1, 0, m - 1, idx + 1, m - 1, -1);
A[X[iq]] = V[iq];
idx = lower_bound(cmp.begin(), cmp.end(), mp(A[X[iq]], X[iq])) - cmp.begin();
vv = get(1, 0, m - 1, idx, idx);
set_val(1, 0, m - 1, idx, X[iq] - vv);
incr(1, 0, m - 1, idx + 1, m - 1, +1);
outp.push_back(T[1].maxi);
}
return outp;
}
