该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Alice 和 Bob 正在分糖果，他们面前摆着 $n$ 堆糖果排成一行，第 $i$ 堆有 $d_i$颗糖果。他们决定这样分配：

• 从最左边开始连续若干堆分给 Alice；

• 然后中间连续若干堆留作 备用（可能为空）；

• 最后最右边连续若干堆分给 Bob。

但为了公平，他们要求 Alice 和 Bob 最终得到的糖果总数必须相等，并且希望这个相等的糖果数 尽可能多。

请你帮助他们计算出，在满足要求的情况下，Alice（或 Bob）最多能得到多少颗糖果。

注意： 某些部分可以为空，例如 Alice 或 Bob 可以没有糖果（总数为 $0$），所以至少存在一种方案（Alice 和 Bob 都不拿，所有糖果留作备用）。

糖果数量可能很大，请使用 64 位整数进行计算。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量$t(1≤t≤1000)$。

每个测试用例的第一行都包含一个整数$n$， 表示糖果堆的数量。$(n≤2 \cdot 10^5)$

每个测试用例的第二行都包含$n$个整数$d_1，d_2，...，d_n （1≤d_i≤10^9）$，表示每堆糖果的数量。

每个测试$n$的总和不超过$2 \cdot 10^{5}$。

输出格式

对于每个测试用例，输出一个整数表示 Alice 和 Bob 能够得到的相等糖果总数的最大值。（每个测试用例结尾必须输出一个换行符）

样例

3
5
1 3 1 1 4
5
1 3 2 1 4
3
4 1 2

5
4
0

样例解释

对于第一组样例： 只有一种可能的拆分能使 Alice和Bob能得到的相等糖果总数 最大化： [1,3,1],[ ],[1,4]。

对于第二组样例： 唯一可能性是： [1,3],[2,1],[4]。

对于第三组样例： 只有一种分割糖果堆的方法： [ ],[4,1,2],[ ]。