P8684 [Lanqiao Cup 2019 NOI Qualifier B] Psionic Energy Transfer

In the game *StarCraft II*, the High Templar is an important AOE unit for the Protoss and plays a key role in the mid and late game. Its skill “Psionic Storm” can consume a large amount of psionic energy to deal devastating damage to enemy troops in an area. It is often used to fight against Terran bio armies and low-HP Zerg units such as Hydralisks and Mutalisks.

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.

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 $T$ lines. Each line contains one integer, representing the answer for each query in order.

**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