的 美女 长度为 $$$m$$$(其中 $$$m \ge 2$$$)的数组 $$$b$$$ 的 被定义为所有索引对 $$$i$$$ 和 $$$j$$$ 上 $$$b_j - b_i$$$ 的最大值,使得 $$$1\le i \lt j\le m$$$。更正式地说,它等于 $$$\max\limits_{1\le i \lt j\le m} (b_j - b_i)$$$。请注意,如果数组严格递减,则美观度可能为负。
hao 和 Alex 在长度为 $$$n$$$ 的数组 $$$a$$$ 上玩回合制游戏。最初,数组的所有元素都被解锁。选手们轮流轮流, 郝先行.
- 轮到Hao了,他从数组$$$a$$$中选择一个未锁定的元素并将其删除。
- 轮到 Alex 时,他从数组 $$$a$$$ 中选择一个未锁定的元素并将其锁定(因此Hao 无法再将其删除)。
游戏继续进行,直到 $$$a$$$ 的所有元素都被锁定或删除。可以证明,游戏持续了$$$n$$$个回合,并且$$$\left\lfloor \frac{n}{2} \right\rfloor$$$元素最终将保持锁定在数组$$$a$$$中。
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$$$。
输出
对于每个测试用例,如果Hao 和Alex 都发挥最佳,则输出一个表示最终数组的美丽程度的整数。
示例
输入复制
655 1 2 3 443 1 2 1107 1 3 5 8 2 8 3 5 161 1 4 5 1 499 9 8 2 4 4 3 5 341000000000 1 2 3
输出复制
1-2531-999999998
注意
在第一个测试用例中,游戏可以如下进行。 粗体元素 被 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]$$$。美丽之处在于,所有索引对 $$$i$$$ 和 $$$j$$$ 之间的最大差异 $$$b_j - b_i$$$ 使得 $$$1\le i \lt j\le 5$$$ 等于 $$$b_3 - b_1 = 8 - 3 = 5$$$。