Problem Background

In the game "StarCraft II," the High Templar, as a significant AOE unit for the Protoss, plays a crucial role in the late game. Their skill, "Psionic Storm," can consume a large amount of psionic energy to inflict devastating damage on enemy forces within a certain area. It is often used to counter low-health units like the Terran's bio units and Zerg's Hydralisks and Mutalisks.

Problem Description

You control $n$ High Templars, conveniently labeled as $1, 2, \cdots, n$. Each High Templar requires a certain amount of psionic energy to fight, with each having a psionic value $a_i$ indicating the amount of psionic energy they possess ($a_i$ being non-negative means the High Templar has $a_i$ points of excess psionic energy beyond their optimal state, while $a_i$ being negative means the High Templar needs $-a_i$ points of psionic energy to reach their optimal fighting condition). Now, the system has granted your High Templars a capability: psionic transmission. You can choose an $i \in [2, n-1]$, and if $a_i \ge 0$, the two adjacent High Templars, $i-1$ and $i+1$, will each draw $a_i$ points of psionic energy from $i$; if $a_i < 0$, the two adjacent High Templars, $i-1$ and $i+1$, will each give $-a_i$ points of psionic energy to $i$. Formally, this operation transforms $(a_{i-1}, a_i, a_{i+1})$ into $(a_{i-1} + a_i, -a_i, a_{i+1} + a_i)$.

Psionic energy is a highly efficient but also very dangerous and unstable combat tool. Too much or too little psionic energy for a High Templar is undesirable. Define the instability of a group of High Templars as $\max_{i=1}^n \{|a_i|\}$. You are to minimize the instability of your group of High Templars through an unlimited number of psionic transmission operations.

Input Format

The input contains multiple queries. The first line of input contains a positive integer $T$ indicating the number of queries.

Each query is inputted as follows:

The first line of each query contains a positive integer $n$, the number of High Templars.

The next line contains $n$ numbers $a_1, a_2, \cdots, a_n$.

Output Format

Output $T$ lines. Each line should contain an integer representing the answer for each query.

Sample Input and Output

Input Sample #1

3 3
5 -2 3
4
0 0 0 0
3
1 2 3

Output Sample #1

3 0 3

Input Sample #2

3 4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1

Output Sample #2

5 7 4

Input Sample #3

See file trans3.in.

Output Sample #3

See file trans3.ans.

Notes/Hints

[Sample Explanation]

For the first query:

After performing the transmission operation on the 2nd High Templar, $a_1 = 3$, $a_2 = 2$, $a_3 = 1$. The answer is $3$.

For the second query:

All High Templars have exactly the psionic energy needed for their optimal combat state.

[Data Range and Constraints]

For all test cases, $T \le 3$, $3 \le n \le 3 \times 10^5$, $|a_i| \le 10^9$.

Your program will be tested with 25 test cases, each with the following constraints:

This problem is the J题 from the 2019 LanQiao Cup Provincial Competition, Group B.

见题面 Input 部分

见题面 Output 部分