在游戲《星際爭霸 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
2019年精選賽題 2299 2300 2301 2302 2304 2305 2306 2307 2308 2310 2311 2312
2299 2300 2301 2302 2304 2305 2306 2307 2308 2310 2311 2312
2299 2300 2301 2302 2304 2305 2306 2307 2308 2310 2311 2312