Description

You control $n$ High Templars, labeled $1,2,\cdots,n$ for convenience. Each High Templar needs a certain amount of psionic energy to fight. Each one has a psionic value $a_i$ representing how much psionic energy it has ($a_i \ge 0$ means this High Templar has $a_i$ extra psionic energy beyond the best state; $a_i < 0$ means this High Templar still needs $-a_i$ psionic energy to reach the best fighting state).

Now the system gives your High Templars an ability: transferring psionic energy. Each time, you may choose an $i \in [2,n-1]$.

• If $a_i \ge 0$, then the two adjacent High Templars, i.e. $i-1$ and $i+1$, will each draw $a_i$ psionic energy from the $i$-th High Templar.
• If $a_i < 0$, then the two adjacent High Templars, i.e. $i-1$ and $i+1$, will each give $-a_i$ psionic energy to the $i$-th High Templar.

Formally,

$$(a_{i-1},a_i,a_{i+1})\leftarrow (a_{i-1}+a_i,-a_i,a_{i+1}+a_i).$$

Psionic energy is a very efficient combat tool, but it is also dangerous and unstable. Having too much or too little psionic energy is bad. Define the instability of a group of High Templars as $\max\limits_{i=1}^n\{|a_i|\}$. Please perform the transfer operation any number of times to minimize the instability of the group you control.

Input Format

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

Then the queries follow.

For each query, the first line contains a positive integer $n$, indicating 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 contains one integer, representing the answer for each query in order.

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

3
0
3

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

5
7
4

见文件trans3.in。

见文件trans3.ans。

Hint

Sample Explanation

For the first query:

After performing the transfer operation on the High Templar No. $2$, we get $a_1=3$, $a_2=2$, $a_3=1$. The answer is $3$.

For the second query:

The psionic energy of this group of High Templars is exactly enough for them to reach the best fighting state.

Constraints

For all testcases, $T \le 3$, $3 \le n \le 3\times10^5$, $|a_i| \le 10^9$.

During judging, $25$ testcases will be used to test your program, and each testcase has the following limits:

Lanqiao Cup 2019 Provincial Contest B Group, Problem J.

Translated by ChatGPT 5