#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;
#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif
const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;
int n, m, q, a[mn], st[mn << 2], lz[mn << 2];
pii v[mn];
void down(int id, int l, int r){
if(l == r || !lz[id]) return;
lz[id << 1] += lz[id];
lz[id << 1 | 1] += lz[id];
st[id << 1] += lz[id];
st[id << 1 | 1] += lz[id];
lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val){
if(l > v || r < u) return;
if(l >= u && r <= v){
st[id] += val;
lz[id] += val;
return;
}
down(id, l, r);
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void add(int pos, int val){
}
void del(int val, int pos){
}
namespace sub2{
int bit[mn];
void add(int u, int val){
while(u <= m){
bit[u] += val;
u += (u & -u);
}
}
int get(int u){
int r = 0;
while(u){
r += bit[u];
u -= (u & -u);
}
return r;
}
vector <int> sol() {
vector <int> ans;
for(int i = 1; i <= q; i++){
a[v[i].se] = v[i].fi;
int r = 0;
for(int i = 1; i <= n; i++){
add(a[i], 1);
r = max(r, get(m) - get(a[i]));
}
for(int i = 1; i <= n; i++) add(a[i], -1);
ans.push_back(r);
}
return ans;
}
}
// ans = max(cnt[i]) với cnt[i] = số cặp nghịch thế của i
vector <int> countScans(vector <int> A, vector <int> X, vector <int> V){
n = A.size(), q = X.size();
for(int i = 1; i <= n; i++) a[i] = A[i - 1];
for(int i = 1; i <= q; i++) v[i] = {V[i - 1], X[i - 1] + 1};
vector <int> comp;
for(int i = 1; i <= n; i++) comp.push_back({a[i]});
for(int i = 1; i <= q; i++) comp.push_back({v[i].fi});
sort(all(comp)); comp.erase(unique(all(comp)), comp.end());
for(int i = 1; i <= n; i++) a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;
for(int i = 1; i <= q; i++) v[i].fi = lower_bound(all(comp), v[i].fi) - comp.begin() + 1;
m = comp.size();
return sub2::sol();
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro
