直接求解答案似乎并不容易，因为需要考虑的大小关系太多了，于是可以尝试二分转为 01 问题。
于是尝试思考，如何判断答案是否 \(\ge w\)。
这个问题并不具有一些特殊的结构，所以可以先考虑一点暴力的解法。
因为答案只与二元组 \((i, j)\) 有关，可以转为图论问题，即对 \(a_j - a_i\ge w(i < j)\) 的 \((i, j)\) 连边，先手赢需要满足最后每一条边都有至少一个点被删除，后手赢需要满足最后存在一条边的两个端点都没被删除，若后手赢则说明答案 \(\ge w\)。
此时可以考虑一些特例。
比如说如果整个图只有一条边 \((1, 2)\)，那么先手是必赢的，因为一个点只会有唯一的配对，后手选取了其中一个，先手就可以删掉另一个。
于是可以知道，若所有点的度数都 \(\le 1\)，先手是必赢的。
那如果存在点的度数 \(\ge 1\)，会发现一旦来到了后手操作，此时后手必赢，因为后手可以先固定下这个点，先手不管删掉哪个点，该点都至少有 \(1\) 个邻点可以固定。
不过上面的分析都是基于让后手先操作的，实际上先手可以先操作一步，于是直接枚举先手第一步删掉哪个点，再进行上面的判定，就可以做到 \(\mathcal{O}(n^2)\) 的复杂度。
考虑继续挖掘性质。
发现如果删掉一个点，对于其他点的度数影响至多 \(-1\)。
那么如果其他点中有度数 \(\ge 3\) 的点，删掉后度数也至少 \(\ge 2\)，一定后手赢。
于是可以根据图中度数 \(\ge 3\) 的点数进行分讨：
- \(\ge 2\)，那么一定有一个点不会被删去，后手必赢。
- \(= 1\)，那么第一步一定删掉这个点。
- \(= 0\)，那么剩余点的度数一定 \(\le 2\)，此时枚举删掉每个点时只遍历这个点的邻点判断即可。
于是 check 就做到了 \(\mathcal{O}(n)\) 的复杂度。
不过刚刚忽略了处理连边的部分，如果边数到了 \(\mathcal{O}(n^2)\) 级别依然不能接受。
分析上面的过程，发现过程中我们只关心一个点的度数是否 \(\ge 3\)。
这说明我们只需要对每个点保留权值最大的 \(3\) 条边，那么就可以维护这个点前面的点权前 \(3\) 小和后面的点权前 \(3\) 大。
时间复杂度 \(\mathcal{O}(n\log V)\)。
#include <bits/stdc++.h>using ll = long long;constexpr ll inf = 1e10;
constexpr int N = 1e5 + 10;int n, a[N];
std::pair<ll, int> now[4], pi[N][6];
int c[N];inline bool check(ll bound) {int cnt = 0, lst = 0;for (int i = 1; i <= n; i++) {c[i] = 0;while (c[i] < 3 && pi[i][c[i]].first >= bound) {c[i]++;}if (c[i] >= 3) {if (lst) {return true;} else {lst = i;}}cnt += c[i] >= 2;}if (cnt == 0) {return false;}if (lst) {for (int i = 1; i <= n; i++) {if (i == lst) {continue;}if (i < lst) {c[i] -= a[lst] - a[i] >= bound;} else {c[i] -= a[i] - a[lst] >= bound;}if (c[i] >= 2) {return true;}}return false;} else {for (int i = 1; i <= n; i++) {if (c[i] == 2) {int _cnt = 1;for (int j = 0; j < 2; j++) {_cnt += c[pi[i][j].second] == 2;}if (cnt == _cnt) {return false;}}}return true;}
}inline void solve() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}now[0] = now[1] = now[2] = {inf, 0};for (int i = 1; i <= n; i++) {for (int j = 0; j < 3; j++) {pi[i][j] = {a[i] - now[j].first, now[j].second};}for (int j = 0; j < 3; j++) {if (a[i] < now[j].first) {for (int k = 2; k > j; k--) {now[k] = now[k - 1];}now[j] = {a[i], i};break;}}}now[0] = now[1] = now[2] = {-inf, 0};for (int i = n; i >= 1; i--) {for (int j = 0; j < 3; j++) {pi[i][3 + j] = {now[j].first - a[i], now[j].second};}for (int j = 0; j < 3; j++) {if (a[i] > now[j].first) {for (int k = 2; k > j; k--) {now[k] = now[k - 1];}now[j] = {a[i], i};break;}}}for (int i = 1; i <= n; i++) {std::sort(pi[i], pi[i] + 6, std::greater<>());}ll l = -1e9, r = 1e9, ans = -1e9;while (l <= r) {ll mid = (l + r) / 2;if (check(mid)) {ans = mid, l = mid + 1;} else {r = mid - 1;}}printf("%lld\n", ans);
}int main() {int t;scanf("%d", &t);while (t--) {solve();}return 0;
}