赛时不会做。知道3个数字时， k 可以等于第二小的，但是没办法推广了。

比如： 5,3,2 k = 2 的时候：

5,3,2
2,3,5
2,5,3
5,2,3

下面不会推广了。麻了。想了很多的错误答案。

比如去找第二小的逆序对，其实只是观察到 3 个数字时这种的是逆序对，然后又是第二小的作为答案，就直接当成结论做了。WA。反正也不知道该咋做，就瞎猜了，樂。

标答

任意三元组 (Max, Min, p)，当 k = max(Max - p, p - Min) 的时候。这时候 p 就可以换到任意一个位置。三元组可以以任意一个顺序排列。

考虑有很多个 p: p1, p2, … pn。当 k = min(max(Max - p1, p1- Min), max(Max - p2, p2 - Min) …) 时，可以构造出任意一种排列方法。

因此，对于所有不在有序后位置的元素，也就是 a[i] != sort(a)[i]。都当做 p，然后去找到最小的 k。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    auto b = a;
    sort(b.begin(), b.end());z
    if (a == b) {
        cout << -1 << endl;return;
    }
    int Min = b[0], Max = b[n-1];
    vector<int> temp;
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) temp.push_back(b[i]);
    }
    int ans = LONG_LONG_MAX;
    for (auto v: temp) {
        ans = min(ans, max(v - Min, Max - v));
    }
    cout << ans << endl;
}
signed main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}