#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <climits>
using namespace std;
using ll = long long;
using db = long double;
using str = string;
using pi = pair <int, int>;
using pl = pair <ll, ll>;
using pd = pair <db, db>;
#define mp make_pair
#define ff first
#define ss second
template <class T> using V = vector <T>;
using vi = V <int>;
using vb = V <bool>;
using vl = V <ll>;
using vd = V <db>;
using vs = V <str>;
using vpi = V <pi>;
using vpl = V <pl>;
using vpd = V <pd>;
template <class T> using PQ = priority_queue <T>;
#define sz(x) (int) size(x)
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define srt(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define emb emplace_back
#define em emplace
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define F0R(i, a) FOR(i, 0, a-1)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define each(e, x) for (auto &e : x)
ll cdiv(ll a, ll b) { return ceil((db) a / b); }
ll fdiv(ll a, ll b) { return floor((db) a / b); }
template <typename T, typename = void>
struct is_iterable : false_type {};
template <typename T>
struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};
void err(string name) {}
template <typename T, typename... Args>
void err(string name, T val, Args... args) {
size_t pos = name.find(',');
string first = (pos == string::npos) ? name : name.substr(0, pos);
string rest = (pos == string::npos) ? "" : name.substr(pos + 2);
cout << first << " = ";
if constexpr (is_iterable<T>::value && !is_same_v<T, string>) {
cout << "{";
bool fst = true;
for (auto const& x : val) {
if (!fst) cout << ", ";
cout << x;
fst = false;
}
cout << "}";
} else {
cout << val;
}
if (rest != "") {
cout << " | ";
err(rest, args...);
} else {
cout << '\n';
}
}
#ifdef LOCAL
#define dbg(...) cout << "[" << __FUNCTION__ << ":" << __LINE__ << "] ", err(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...) 67
#endif
void setIO(string name = "") {
ios::sync_with_stdio(0), cin.tie(0);
if (sz(name)) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
const ll INF = 1e18;
const pi d[4] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353; // 1e9+7;
const int mxN = 2e5+5;
#include "bubblesort2.h"
vector <int> countScans(vector <int> A, vector <int> X, vector <int> V){
// BRUTEFORCE
int n = sz(A);
vi ans;
for (int i = 0; i < sz(X); i++) {
A[X[i]] = V[i];
int c = 0;
vi mn(n+1);
mn[n] = INT_MAX;
for (int i = n-1; i >= 0; i--) mn[i] = min(mn[i+1], A[i]);
for (int i = 0; i < n; i++) c += (A[i] > mn[i]);
ans.emb(c);
}
return ans;
}
