Description

DreamGrid 和 BaoBao 正在玩一个游戏。游戏中有 $n$ 名士兵，编号从 $1$ 到 $n$。第 $i$ 个士兵的战斗力为 $a_i$。DreamGrid 和 BaoBao 将根据以下规则把士兵分成若干个队伍：

• 一个队伍必须由 1 或 2 名士兵组成。
• 每个士兵必须属于且仅属于一个队伍。
• 如果一个队伍由两名士兵组成（假设他们是第 $i$ 个和第 $j$ 个士兵），则必须满足 $|i - j| = 1$。

一个队伍的战斗力定义为队伍成员的战斗力之和。为了公平起见，他们希望在分组后最大队伍战斗力与最小队伍战斗力之间的差值最小化。你需要找出这个最小的差值。

Input Format

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示士兵的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$)，其中 $a_i$ 表示第 $i$ 个士兵的战斗力。

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

Output Format

对于每个测试用例输出一行，包含一个整数，表示最大队伍战斗力与最小队伍战斗力之间的最小差值。

3
5
-1 4 2 1 1
4
1 3 2 4
1
7

1
2
0

Hint

我们现在解释第一个样例测试用例。所有可能的分组如下所示。

所以答案是 $\min(5, 5, 5, 7, 2, 7, 1, 2) = 1$。

题面翻译由 ChatGPT-4o 提供。