CF2156E.Best Time to Buy and Sell Stock

一个长度为 $m$ 的数组 $b$（其中 $m \ge 2$）的美丽值定义为所有下标对 $i$ 和 $j$ 满足 $1\le i < j\le m$ 时的最大值 $b_j - b_i$。更正式地，其等于 $\max\limits_{1\le i < j\le m} (b_j - b_i)$。注意，如果该数组严格递减，美丽值可能为负数。

Hao 和 Alex 在一个长度为 $n$ 的数组 $a$ 上轮流进行游戏。初始时，数组中所有元素都是未锁定的。两人轮流行动，由 Hao 先手。

• Hao 的回合，他选择一个未锁定的 $a$ 中的元素并将其移除。
• Alex 的回合，他选择一个未锁定的 $a$ 中的元素并将其锁定（之后不能再被移除）。

当所有元素都被锁定或移除后，游戏结束。可以证明游戏恰好持续 $n$ 个回合，最终数组中会恰好剩下 $\left\lfloor \frac{n}{2} \right\rfloor$ 个被锁定的元素。

Hao 希望最终锁定数组的美丽值尽可能小，而 Alex 希望它尽可能大。求当两人都采取最优策略时，最终锁定的元素数组的美丽值。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例组数。

每组测试用例的第一行包含一个整数 $n$（$4 \le n \le 10^5$），表示数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示当两人均采取最优策略时最终锁定数组的美丽值。

在第一个测试用例中，游戏可能如下进行。加粗的元素表示已被 Alex 锁定：

• 第 1 回合（Hao）：移除元素 $1$（在第 $2$ 位），剩下 $[5, 2, 3, 4]$。
• 第 2 回合（Alex）：锁定元素 $3$（在第 $3$ 位），剩下 $[5, 2, \mathbf{3}, 4]$。
• 第 3 回合（Hao）：移除元素 $2$（在第 $2$ 位），剩下 $[5, \mathbf{3}, 4]$。
• 第 4 回合（Alex）：锁定元素 $4$（在第 $3$ 位），剩下 $[5, \mathbf{3}, \mathbf{4}]$。
• 第 5 回合（Hao）：移除元素 $5$（在第 $1$ 位），剩下 $[\mathbf{3}, \mathbf{4}]$。

最终锁定数组 $b = [3, 4]$ 的美丽值等于 $b_2 - b_1 = 4 - 3 = 1$。

在第二个测试用例中，答案可能为负数：

• 第 1 回合（Hao）：移除元素 $2$（在第 $3$ 位），剩下 $[3, 1, 1]$。
• 第 2 回合（Alex）：锁定元素 $1$（在第 $2$ 位），剩下 $[3, \textbf{1}, 1]$。
• 第 3 回合（Hao）：移除元素 $1$（在第 $3$ 位），剩下 $[3, \textbf{1}]$。
• 第 4 回合（Alex）：锁定元素 $3$（在第 $1$ 位），剩下 $[\textbf{3}, \textbf{1}]$。

最后锁定数组 $b = [3, 1]$ 的美丽值为 $b_2 - b_1 = 1 - 3 = -2$。

在第三个测试用例中，假设两人均采取最优操作，最终锁定的数组可能是 $b = [3, 5, 8, 5, 1]$。其美丽值，即所有下标满足 $1 \le i < j \le 5$ 时 $b_j - b_i$ 的最大值，为 $b_3 - b_1 = 8 - 3 = 5$。

由 ChatGPT 5 翻译