3348. 纪念我们的芙)(兰达

【问题描述】

为我们的芙)(兰达上香!   

当然我们这次的猪脚并不是芙兰达,而是我们的男主上条当麻?????

众所不周知,当麻后宫无数,从左到右从未失手,本来炮姐还是不在意这件事的。

但是!上条先生有一天说了一句话“君子不立于危墙之下,还是远离这个哔哩哔哩”!太过分了!

御坂小姐是绝对忍不了的,但是呢,Misaka是一个温柔可爱的女子,于是她决定把上条先生大卸两块,没错是两块!!

上条先生的长度为n,并且每个单位长度都有一个相对应的重量,炮姐希望将他劈成两部分后,

两个部分中的最大重量之差的绝对值最大(显然两个部分均不能为空啊,岂能放过他),但是炮姐最近在忙着考试

不知道怎么劈最好,于是找到了我们ACMer,你能帮助炮姐吗?(如果你不能帮助她 会死的很惨!)。


【输入形式】

第一行一个t (t<=5)表示数据组数

每组数据第一行一个n (2<=n<=106) , 表示上条当麻的长度,接下来一行有n个数,表示上条每个单位长度的重量

(0 <= a[i] <= 2147483648)。


【输出形式】

输出切成两部分后,每部分的重量的最大值之差的绝对值最大是多少。

【样例输入】

1
4
3 4 1 6

【样例输出】

3

【样例说明】
【评分标准】

难度等级: 0
总通过次数: 51
总提交次数: 56