#include <bits/stdc++.h>
using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */
long long cnt;
vector<int> seq;
vector<int> seqtmp;
// 这个函数的功能是计算答案（即最少花费的金钱）
// n：表示序列长度
// a：存储整个序列 a
// 返回值：最少花费的金钱（需要注意，返回值的类型为 64 位有符号整数）
void mergeSort(int l,int r)
{
    if(l == r)
        return;
    int mid = (l+r) >> 1;
    mergeSort( l , mid );
    mergeSort(mid + 1,r);
    int p = l;
    int q = mid + 1;
    for(int i=l; i<=r; i++)
    {
        if(seq[p] <= seq[q] && p<=mid || q > r)
//p<=mid可以进行前半序列插入
//q > r同理 
            seqtmp[i] = seq[p++];
        else
        {
            seqtmp[i] = seq[q++];
            cnt = cnt + mid + 1 - p; 
        }
    }
    for(int i=l; i<=r; i++)
    {
        seq[i] = seqtmp[i];
    }

}



long long getAnswer(int n, vector<int> a)
{
    seq = a;
    seqtmp.resize(n);
    cnt = 0;
    mergeSort(0,n-1);
    return cnt;

}

// ================= 代码实现结束 =================

int main()
{
    int n, tmp;
    vector<int> a;
    a.clear();
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &tmp);
        a.push_back(tmp);
    }
    long long ans = getAnswer(n, a);
    cout << ans << '\n';
    return 0;
}

当进行TwoWayMerge的时候，如果右边的数组插入左边的数组，如果右边

seq[p] > seq[q] 

则 情况类似于 1 9 10
5 6 7
插入到
1 5
此时逆序对有（5,9） （5,10）
为前半序列未插入时候的空位，因为空位的数量就是5 小于前列未插入数的数目，所以为

int cnt = 0;
cnt = cnt +mid + 1 - p;

当前半序列都插满的时候
1 5 6 7

mid + 1 - p 就是前半序列未插入的数量 每次后半序列插入都和前半序列未插入的数构成逆序对。