1466: 吃糖果

一张桌子上从左到右放着 $n$ 粒糖果。这些糖果从左到右依次编号。第 $i$-th 颗糖果的重量是 $w_i$。爱丽丝和鲍勃两人吃糖。

爱丽丝可以从左边开始吃任意数量的糖果(她不能跳着吃，要连续吃)。

鲍勃可以从右边吃任意数量的糖果(他不能跳着吃，要连续吃)。

当然，一颗糖只能被其中一个人吃掉。若最终只剩一颗糖了，则两人都无法吃到这颗糖。

他们希望公平看看谁更有运气。即如果两个人吃相同数量的糖果，最大的价值差是多少？

说明：价值差为两人分别吃的糖果的价值和的差值的绝对值。

每个测试用例的第一行包含一个整数 $n$ ( $1$ ≤ $n$ ≤ $2⋅10^5$ ) - 桌面上的糖果数量。

每个测试用例的第二行包含 $n$ 个整数 $w_1,w_2,...,w_n$ ( $1$ ≤ $w_i$ ≤ $10^9$ )- 从左到右糖果的重量。

对于每个测试用例，打印一个整数 $a$ - 在满足条件的情况下，爱丽丝和鲍勃最终的最大价值差。

3
10 20 10

0