#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'
#include "bubblesort2.h"
struct FenwickTree{
vector<int> a; int n, s;
FenwickTree(int N){ a.resize((n=N)+1); }
void add(int i, int v){
for(++i; i<=n; i+=i&-i) a[i] += v;
}
int get(int i){
for(s=0; i>=1; i-=i&-i) s += a[i];
return s;
}
int get(int l, int r){ return get(r+1) - get(l); }
int lower(int v){
int i = 0;
for(s=1<<20; s; s/=2) if(i+s<=n && a[i+s]<v) v -= a[i+=s];
return i;
}
};
const int INF = 1e7;
struct SegmentTree{
vector<int> a, b; int sz = 1;
const int ID = -INF;
SegmentTree(vector<int> &v){
while(sz < (int)v.size()) sz += sz;
a.assign(2*sz, ID);
b.resize(2*sz);
build(v, 0, 0, sz);
}
void build(vector<int> &v, int x, int lx, int rx){
if(rx-lx==1){
if(lx < (int)v.size()) a[x] = v[lx];
return;
}
int mx = (lx + rx) / 2;
build(v, 2*x+1, lx, mx);
build(v, 2*x+2, mx, rx);
a[x] = max(a[2*x+1], a[2*x+2]);
}
void update(int i, int v, int x, int lx, int rx){
if(rx-lx==1) return void(a[x] = v);
int mx = (lx + rx) / 2; v -= b[x];
if(i < mx) update(i, v, 2*x+1, lx, mx);
else update(i, v, 2*x+2, mx, rx);
a[x] = b[x] + max(a[2*x+1], a[2*x+2]);
}
void update(int i, int v){ update(i, v, 0, 0, sz); }
void rangeAdd(int l, int r, int v, int x, int lx, int rx){
if(r<=lx || rx<=l) return;
if(l<=lx && rx<=r){
a[x] += v;
b[x] += v;
return;
}
int mx = (lx + rx) / 2;
rangeAdd(l, r, v, 2*x+1, lx, mx);
rangeAdd(l, r, v, 2*x+2, mx, rx);
a[x] = b[x] + max(a[2*x+1], a[2*x+2]);
}
void rangeAdd(int l, int r, int v){ rangeAdd(l, r+1, v, 0, 0, sz); }
int query(){ return a[0]; }
};
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
vector<array<int, 2>> p(A.size()+X.size());
for(int i=0; i<(int)A.size(); ++i) p[i] = {A[i], i};
for(int i=0; i<(int)X.size(); ++i) p[i+A.size()] = {V[i], X[i]};
sort(p.begin(), p.end());
vector<int> seg(p.size(), -INF), pos(A.size()), res(X.size());
FenwickTree f(p.size());
for(int i=0; i<(int)A.size(); ++i){
array<int, 2> search = {A[i], i};
pos[i] = lower_bound(p.begin(), p.end(), search) - p.begin();
f.add(pos[i], 1);
}
for(int i=0; i<(int)A.size(); ++i) seg[pos[i]] = i - f.get(0, pos[i] - 1);
SegmentTree st(seg);
for(int i=0; i<(int)X.size(); ++i){
array<int, 2> search = {V[i], X[i]};
int j = lower_bound(p.begin(), p.end(), search) - p.begin();
if(pos[X[i]] < j) st.rangeAdd(pos[X[i]], j, 1);
else st.rangeAdd(j, pos[X[i]], -1);
f.add(pos[X[i]], -1);
f.add(j, 1);
st.update(pos[X[i]], st.ID);
st.update(pos[X[i]] = j, X[i] - f.get(0, j-1));
res[i] = st.query();
}
return res;
}
