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