题目背景
在游戏《星际争霸II》中，高阶圣堂武士作为星灵的重要AOE 单位，在 游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对 一片区域内的敌军造成毁灭性的伤害。经常用于对抗人类的生化部队和虫族的 刺蛇飞龙等低血量单位。
问题描述
你控制着n 名高阶圣堂武士，方便起见标为1; 2; ...... ; n。每名高阶圣堂武士 需要一定的灵能来战斗，每个人有一个灵能值ai 表示其拥有的灵能的多少（ai 非负表示这名高阶圣堂武士比在最佳状态下多余了ai 点灵能，ai 为负则表示这 名高阶圣堂武士还需要-ai 点灵能才能到达最佳战斗状态）。现在系统赋予了 你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个i 属于2 [2; n - 1]，若 ai >=0 则其两旁的高阶圣堂武士，也就是 i - 1、i + 1 这两名高阶圣堂武士会从 i 这名高圣堂武士这里各抽取ai 点灵能；若ai < 0 则其两旁的高阶圣堂武士， 也就是i - 1;i + 1 这两名高阶圣堂武士会给i 这名高阶圣堂武士?ai 点灵能。形式化来讲就
灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂 武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为
请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武 士的不稳定度最小。
输入格式
本题包含多组询问。输入的第一行包含一个正整数T 表示询问组数。
接下来依次输入每一组询问。
每组询问的第一行包含一个正整数n，表示高阶圣堂武士的数量。
接下来一行包含n 个数a1; a2; ……..; an。
输出格式
输出T 行。每行一个整数依次表示每组询问的答案。
样例输入
1
2
3
4
5
6
7
|
3
3
5 -2 3
4
0 0 0 0
3
1 2 3
|
样例输出
样例说明
对于第一组询问：
对2 号高阶圣堂武士进行传输操作后a1 = 3
对于第二组询问：
这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。
样例输入
1
2
3
4
5
6
7
|
3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1
|
样例输出
样例输入
1
2
3
4
5
6
7
|
3
5
6 -4 2 -7 3
10
-99 -53 43 80 -83 72 99 78 -63 -9
100
373837389 225627048 -847064399 487662607 579717002 903937892 -89313283 134706789 259978604 399131737 298183518 62083619 -444218530 403702220 358088455 -973959249 -637339048 -736509394 -552801709 -98262597 -532577703 -393599463 762744971 -683270041 716127816 -991756495 734780346 27919355 -421469435 258728334 844409214 -270792553 -490888330 133696186 843888283 -35439761 -73481392 -118968548 269164182 978558860 522378250 -979427259 -330256906 235192566 -652699569 -708569352 -778693386 241745676 583226906 121065292 -503683097 599394257 405122877 437067802 238539735 -957745973 -843677563 -690555937 908484805 940157941 524765035 730436972 -17856720 -530595388 -727773574 617781285 491720304 -779040285 -298295760 -699402143 230749576 404009775 126806094 -140842651 198136484 681875881 997449600 898972467 -239590302 -62193410 866009412 -401154712 -276085482 593177187 -236793216 487533624 75511548 -446699920 -869912037 -330666015 268937148 -430325605 -635949275 361887555 -855294881 87004526 782523543 -69083645 -965396597 -880697065
|
样例输出
数据规模与约定
对于所有评测用例:
评测时将使用25 个评测用例测试你的程序，每个评测用例的限制如下：
注意：本题输入量较大请使用快速的读入方式。