膜拜一下机房同年级金钩爷 ymz，提供的思路清晰简洁。
因此特地开一篇题解记录，而不是我的题解合集里面吃灰。

再安利一下 集训 ARC 题解合集，最近一直在更这个，免得被喷说最近啥都没做。

注意题目中是对 $[1,a_i]$ 进行一轮冒泡排序，并非一轮排序。
一次操作会使得 $P$ 的一段前缀 $P_{1,\dots,a_i}$ 中的元素发生位移。
发现会往后移动的元素都是前缀最大值，而其他元素会往前移动恰好一位。
观察性质，发现 $a_i \leq a_{i+1}$，所以某个数一旦开始移动，它就会持续移动，直到到达它应该到的位置。
并且，每一次交换 $a_{i} \lt a_{i+1}$，都只会让答案 $-1$。

所以，我们考虑每一个数 $P_i$ 会对答案有怎样的贡献，设它是从第 $k$ 次操作开始移动的，它前面有 $t_i$ 个数比它大。
那么，它对区间 $[k, k + t_i - 1]$ 的贡献就 $+1$，这可以用差分做，但我比较喜欢数据结构所以用了线段树。
用差分估计可以少几十行的。
反正是过了，就当回顾板子，锻炼码力吧。

要开 long long！！！

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 15;
int n, q;
int a[N], p[N], t[N];

int Tr[N];
long long ans = 0;
void add(int x) {
    for (; x; x -= x & -x) Tr[x]++;
}
int query(int x) {
    int res = 0;
    for (; x <= n; x += x & -x) res += Tr[x];
    return res;
}

struct Tree {
    int l, r;
    int flag, sum;
} tr[N << 2];
void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u) {
    if (tr[u].flag) {
        tr[u << 1].flag += tr[u].flag;
        tr[u << 1 | 1].flag += tr[u].flag;
        tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].flag;
        tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].flag;
        tr[u].flag = 0;
    }
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    tr[u].flag = tr[u].sum = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
}

void change(int u, int l, int r) {
    if (l > r) return;
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].flag ++;
        tr[u].sum += (tr[u].r - tr[u].l + 1);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) change(u << 1, l, r);
    if (r > mid) change(u << 1 | 1, l, r);
    pushup(u);
}

int ask(int u, int x) {
    if (tr[u].l == tr[u].r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) return ask(u << 1, x);
    else return ask(u << 1 | 1, x);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
    for (int i = 1; i <= n; i++) {
        t[i] = query(p[i]), ans += t[i];
        add(p[i]);
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) scanf("%d", &a[i]);
    build(1, 1, q);
    for (int i = 1; i <= n; i++) {
        int k = lower_bound(a + 1, a + 1 + q, i) - a;
        change(1, k, min(k + t[i] - 1, q));
    }
    for (int i = 1; i <= q; i++) {
        ans -= ask(1, i);
        printf("%lld\n", ans);
    }
    return 0;
}