#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = (int)5e5 + 5, Q = N, inf = (int)1e9 + 123;
int n, q, order_q[N], order_a[N];
struct It {
struct Node {
int cnt, mx, lz;
Node (int _cnt = 0, int _mx = -inf, int _lz = 0) : cnt(_cnt), mx(_mx), lz(_lz) {}
Node operator+ (const Node &_) const { return Node(cnt + _.cnt, max(mx, _.mx), 0); }
} node[N << 3];
void true_val (int nd, int Left, int Right) {
if (!node[nd].lz) return ;
node[nd].mx += node[nd].lz;
if (Left != Right) {
node[nd << 1].lz += node[nd].lz;
node[nd << 1 | 1].lz += node[nd].lz;
}
node[nd].lz = 0;
}
void upd_rep (int nd, int Left, int Right, int pos, int val_mx, int val_cnt) {
true_val(nd, Left, Right);
if (pos < Left || Right < pos) return ;
if (Left == Right) {
node[nd] = Node(val_cnt, val_mx, 0);
return ;
}
int mid = (Left + Right) >> 1;
upd_rep(nd << 1, Left, mid, pos, val_mx, val_cnt);
upd_rep(nd << 1 | 1, mid + 1, Right, pos, val_mx, val_cnt);
node[nd] = node[nd << 1] + node[nd << 1 | 1];
}
void upd_add (int nd, int Left, int Right, int l, int r, int val) {
true_val(nd, Left, Right);
if (r < Left || Right < l) return ;
if (l <= Left && Right <= r) {
node[nd].lz = val; true_val(nd, Left, Right);
return ;
}
int mid = (Left + Right) >> 1;
upd_add(nd << 1, Left, mid, l, r, val);
upd_add(nd << 1 | 1, mid + 1, Right, l, r, val);
node[nd] = node[nd << 1] + node[nd << 1 | 1];
}
int get_cnt (int nd, int Left, int Right, int l, int r) {
true_val(nd, Left, Right);
if (r < Left || Right < l) return 0;
if (l <= Left && Right <= r) return node[nd].cnt;
int mid = (Left + Right) >> 1;
return get_cnt(nd << 1, Left, mid, l, r) + get_cnt(nd << 1 | 1, mid + 1, Right, l, r);
}
} it;
struct Vec_ele {
int val, pos_a, dstnct;
Vec_ele (int _val = 0, int _pos_a = 0, int _dstnct = 0) : val(_val), pos_a(_pos_a), dstnct(_dstnct) {}
bool operator< (const Vec_ele &_) const { return make_pair(val, pos_a) < make_pair(_.val, _.pos_a); }
};
vector<int> countScans (vector<int> a, vector<int> x, vector<int> v) {
n = (int)a.size(); q = (int)x.size();
vector<Vec_ele> vec;
for (int i = 0; i < n; ++i) vec.pb( Vec_ele(a[i], i, i) );
for (int i = 0; i < q; ++i) vec.pb( Vec_ele(v[i], x[i], i + n) );
sort(vec.begin(), vec.end() );
for (int i = 0; i < (int)vec.size(); ++i) {
int pos_a = vec[i].pos_a, dstnct = vec[i].dstnct;
if (dstnct < n) {
order_a[dstnct] = i;
int up_val = pos_a - it.get_cnt(1, 0, (int)vec.size() - 1, 0, i);
it.upd_rep(1, 0, (int)vec.size() - 1, order_a[dstnct], up_val, 1);
}
else order_q[dstnct - n] = i;
}
vector<int> ret(q);
for (int i = 0; i < q; ++i) {
it.upd_add(1, 0, (int)vec.size() - 1, order_a[ x[i] ], (int)vec.size() - 1, 1);
it.upd_rep(1, 0, (int)vec.size() - 1, order_a[ x[i] ], -inf, 0);
order_a[ x[i] ] = order_q[i];
it.upd_add(1, 0, (int)vec.size() - 1, order_a[ x[i] ], (int)vec.size() - 1, -1);
int up_val = x[i] - it.get_cnt(1, 0, (int)vec.size() - 1, 0, order_a[ x[i] ]);
it.upd_rep(1, 0, (int)vec.size() - 1, order_a[ x[i] ], up_val, 1);
ret[i] = it.node[1].mx;
}
return ret;
}
