Problem B
Soldier Game

DreamGrid and BaoBao are playing a game. There are $n$ soldiers in the game, numbered from $1$ to $n$. The $i$-th soldier has a power value of $a_ i$. DreamGrid and BaoBao are going to divide the soldiers into several teams according to the rules below:

• A team must consist of 1 or 2 soldiers.

• Every soldier must belong to exactly 1 team.

• If a team consists of two soldiers $i$ and $j$ then it must be $|i-j| = 1$.

The power value of a team is defined as the sum of the team members’ power values. For the sake of fairness, they want to minimize the difference between the maximum team power value and the minimum team power value after the division. You are asked to find the minimum this difference.

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the number of soldiers.

The second line contains $n$ integers $a_1, a_2, ... , a_ n$ ($-10^9 \le a_ i \le 10^9$), where $a_ i$ indicates the power value of the $i$-th soldier.

It is guaranteed that the sum of $n$ in all test cases will not exceed $10^6$.

Output

For each test case output one line containing one integer, indicating the minimum difference between the maximum team power value and the minimum team power value.

Explanation

All possible divisions of the first sample case are listed below.

So the answer is $\min (5, 5, 5, 7, 2, 7, 1, 2) = 1$.

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

1
2
0