#P18627. Soldier Game

Soldier Game

Soldier Game

DreamGrid 和 BaoBao 正在玩一个有 nn 名士兵的游戏。士兵按顺序编号为 1,…,n1,\ldots,n,第 ii 名士兵的战斗力为 aia_i。

他们要将所有士兵分成若干队,满足:

  • 每队只能包含一名或两名士兵;
  • 每名士兵必须且只能属于一队;
  • 如果第 ii 名和第 jj 名士兵属于同一个两人队,那么必须有 ∣i−j∣=1|i-j|=1,即两人原编号相邻。

一支队伍的战斗力是队员战斗力之和。为了公平,他们希望最强队伍与最弱队伍的战斗力之差尽可能小。

请计算这个差值的最小可能值。士兵的战斗力可以是负数。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例的第一行包含整数 nn。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n。

数据范围

  • 1≤n≤1051\le n\le10^5;
  • −109≤ai≤109-10^9\le a_i\le10^9;
  • 一个输入文件中,所有测试用例的 nn 之和不超过 10610^6。

输出格式

对每个测试用例输出一行,包含最强队伍与最弱队伍战斗力差值的最小可能值。

样例输入 1

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

样例输出 1

1
2
0

样例解释

第一个测试用例的全部八种划分如下。斜杠分隔不同队伍。

队伍划分 最强与最弱之差
[-1] / [4] / [2] / [1] / [1] 5
[-1] / [4] / [2] / [1,1]
[-1] / [4] / [2,1] / [1]
[-1] / [4,2] / [1] / [1] 7
[-1,4] / [2] / [1] / [1] 2
[-1] / [4,2] / [1,1] 7
[-1,4] / [2] / [1,1] 1
[-1,4] / [2,1] / [1] 2

最小值为1。