根据标程思路，下面给出本题的详细题解。

题意回顾

给定一个长度为 $n$ 的排列 $p_1, p_2, \dots, p_n$。
对于每个位置 $i$，可以选择 $a_i = p_i$ 或 $a_i = 2n - p_i$。目标是使数组 $a$ 的逆序对数最少，求该最小值。

核心观察

考虑排列中的最小值 $1$，设其所在位置为 $i$。

• 若选择 $a_i = 1$，则 $a_i$ 是整个数组的最小值，它与左边所有元素（共 $i-1$ 个）都构成逆序对，与右边元素不构成任何逆序对，贡献为 $i-1$。
• 若选择 $a_i = 2n - 1$，则 $a_i$ 变为最大值，它与右边所有元素（共 $n-i$ 个）构成逆序对，与左边无逆序对，贡献为 $n-i$。

这两个选择带来的逆序对数量仅与 $i$ 的位置有关，与其他元素的具体选择完全无关。因此，为了最小化总逆序对数，我们可以直接贪心地选择贡献较小的方案，即取 $\min(i-1,\, n-i)$。

之后，将元素 $1$ 从原排列中移除，剩余 $n-1$ 个元素相对大小关系不变，相当于原排列中的 $2$ 变成了新的最小值 $1'$，问题规模缩小为 $n-1$，且与原问题完全同构。递归地应用上述策略即可得到全局最优解。

算法步骤

上述过程等价于：对排列中的每个元素 $p_i$，分别计算它左侧比 $p_i$ 大的元素个数 $\text{lbigger}_i$ 和右侧比 $p_i$ 大的元素个数 $\text{rbigger}_i$，然后将 $\min(\text{lbigger}_i,\ \text{rbigger}_i)$ 累加到答案中。

为什么这样可以？
当按照元素值从小到大的顺序依次处理时，对于当前最小值 $x$，它左侧比 $x$ 大的元素个数就是 $\text{lbigger}_x$，右侧比 $x$ 大的元素个数就是 $\text{rbigger}_x$。移除 $x$ 后，剩下的元素中，原来的 $x+1$ 成为新的最小值，它的 $\text{lbigger}$ 和 $\text{rbigger}$ 在当前剩余集合中仍保持原来的数值（因为移除的 $x$ 比它小，不影响比它大的计数）。因此，对所有元素独立计算并取 $\min$ 再求和即得到答案。

实现细节

由于 $\sum n \le 5000$，可以在 $O(n^2)$ 时间内直接计算。
对于每个位置 $i$：

• $\text{lbigger}_i =$ $\{j \mid 1 \le j < i,\ p_j > p_i\}$ 的数量。
• $\text{rbigger}_i =$ $\{j \mid i < j \le n,\ p_j > p_i\}$ 的数量。

然后累加 $\min(\text{lbigger}_i,\ \text{rbigger}_i)$。

也可以用树状数组优化到 $O(n \log n)$，但本题数据范围不需要。

正确性证明（归纳）

1. 当 $n=1$ 时，逆序对数为 $0$，公式正确。
2. 假设对长度为 $n-1$ 的排列，按上述方法得到的值是最小逆序对数。
3. 对于长度为 $n$ 的排列，取最小值 $1$ 所在位置 $i$，无论其他元素如何选择，$1$ 变为 $1$ 或 $2n-1$ 造成的逆序对贡献是独立的，贪心选择 $\min(i-1, n-i)$ 不会使总答案更劣。移除 $1$ 后，剩余部分的最优解由归纳假设给出。

因此算法正确。

复杂度

• 时间复杂度：每个测试用例 $O(n^2)$，总复杂度 $O(\sum n^2) \le 2.5 \times 10^7$，在时限内。
• 空间复杂度：$O(n)$。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n);
        for (int i = 0; i < n; ++i) {
            cin >> p[i];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int lbigger = 0, rbigger = 0;
            for (int j = 0; j < i; ++j) {
                if (p[j] > p[i]) lbigger++;
            }
            for (int j = i + 1; j < n; ++j) {
                if (p[j] > p[i]) rbigger++;
            }
            ans += min(lbigger, rbigger);
        }
        cout << ans << " \n";
    }
    return 0;
}