在游戲《星際爭霸 II》中，高階圣堂武士作為星靈的重要 AOE 單位，在 游戲的中后期發(fā)揮著重要的作用，其技能”靈能風暴“可以消耗大量的靈能對 一片區(qū)域內(nèi)的敵軍造成毀滅性的傷害。經(jīng)常用于對抗人類的生化部隊和蟲族的 刺蛇飛龍等低血量單位。
你控制著 n 名高階圣堂武士，方便起見標為 1, 2, · · · , n。每名高階圣堂武士 需要一定的靈能來戰(zhàn)斗，每個人有一個靈能值 ai 表示其擁有的靈能的多少(ai 非負表示這名高階圣堂武士比在最佳狀態(tài)下多余了 ai 點靈能，ai 為負則表示這 名高階圣堂武士還需要 ?ai 點靈能才能到達最佳戰(zhàn)斗狀態(tài))?，F(xiàn)在系統(tǒng)賦予了 你的高階圣堂武士一個能力，傳遞靈能，每次你可以選擇一個 i ∈ [2, n ? 1]，若 ai ≥ 0 則其兩旁的高階圣堂武士，也就是 i ? 1、i + 1 這兩名高階圣堂武士會從 i 這名高階圣堂武士這里各抽取 ai 點靈能;若 ai < 0 則其兩旁的高階圣堂武士， 也就是 i ? 1, i + 1 這兩名高階圣堂武士會給 i 這名高階圣堂武士 ?ai 點靈能。形 式化來講就是 ai?1+ = ai, ai+1+ = ai, ai? = 2ai。
靈能是非常高效的作戰(zhàn)工具，同時也非常危險且不穩(wěn)定，一位高階圣堂
武士擁有的靈能過多或者過少都不好，定義一組高階圣堂武士的不穩(wěn)定度為
maxn |ai|，請你通過不限次數(shù)的傳遞靈能操作使得你控制的這一組高階圣堂武 i=1
士的不穩(wěn)定度最小。
本題包含多組詢問。輸入的第一行包含一個正整數(shù) T 表示詢問組數(shù)。 接下來依次輸入每一組詢問。
每組詢問的第一行包含一個正整數(shù) n，表示高階圣堂武士的數(shù)量。 接下來一行包含n個數(shù)a1,a2,··· ,an。
(對于所有評測用例，T ≤ 3，3 ≤ n ≤ 300000，|ai| ≤ 109。)
輸出 T 行。每行一個整數(shù)依次表示每組詢問的答案
3 3 5 -2 3 4 0 0 0 0 3 1 2 3
3 0 3
Tips：
請對本次比賽進行一些描述，公告內(nèi)容應當包含：
比賽的創(chuàng)辦者或組織；
本次比賽的目的或意義；
本次比賽的考點、語言或類型；或其他注意事項及描述等。
至少保證30個漢字長度。