/*
动态求逆序对，可以树套树来写， 将交换操作理解成插入和删除比较好理解， 里层是个区间求和的线段树就好了
或者叫 带修主席树？
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long
#define M 23000
#define mmp make_pair
using namespace std;
int read() {
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}

int ls[M << 8], rs[M << 8], t[M << 8], rt[M], a[M], b[M], cnt, ans, n, q;
int lowbit(int x) {
    return x & (-x);
}

void modify(int &now, int l, int r, int pl, int v) {
    if(l > pl || r < pl) return;
    if(now == 0) now = ++cnt;
    t[now] += v;
    if(l == r) return;
    int mid = (l + r) >> 1;
    modify(ls[now], l, mid, pl, v), modify(rs[now], mid + 1, r, pl, v);
}

void Modify(int x, int pl, int v) {
    for(; x <= n; x += lowbit(x)) modify(rt[x], 1, n, pl, v);
}

int query(int now, int l, int r, int ln, int rn) {
    if(l > rn || r < ln) return 0;
    if(l >= ln && r <= rn) return t[now];
    int mid = (l + r) >> 1;
    return query(ls[now], l, mid, ln, rn) + query(rs[now], mid + 1, r, ln, rn);
}

int Query(int x, int L, int R) {
    if(L > R) return 0;
    int tmp = 0;
    for(; x; x -= lowbit(x)) tmp += query(rt[x], 1, n, L, R);
    return tmp;
}

int main() {
    n = read();
    for(int i = 1; i <= n; i++) a[i] = b[i] = read();
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    for(int i = 1; i <= n; i++) {
        ans += Query(i, a[i] + 1, n);
        Modify(i, a[i], 1);
    }
    cout << ans << "\n";
    q = read();
    while(q--) {
        int x = read(), y = read();
        if(x > y) swap(x, y);
        ans += Query(y - 1, a[x] + 1, n) - Query(x, a[x] + 1, n);
        ans -= Query(y - 1, 1, a[x] - 1) - Query(x, 1, a[x] - 1);
        ans -= Query(y - 1, a[y] + 1, n) - Query(x, a[y] + 1, n);
        ans += Query(y - 1, 1, a[y] - 1) - Query(x, 1, a[y] - 1);
        if(a[x] < a[y]) ans++;
        else if(a[x] > a[y]) ans--;
        Modify(x, a[x], -1), Modify(y, a[y], -1);
        swap(a[x], a[y]);
        Modify(x, a[x], 1), Modify(y, a[y], 1);
        cout << ans << "\n";
    }
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄