AT_agc073_b.[AGC073B] Cyclic Jump

给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \ldots, A_N)$。

你现在位于数轴上的坐标 $0$，可以进行如下操作任意次：

• 任意选择 $A$ 中的一个元素 $A_i$，也可以自由选择正向或负向，然后朝所选方向跳跃距离 $A_i$。

你关注的是满足下列条件的操作序列：

• 至少执行一次操作，且最终回到坐标 $0$。
• 在跳跃过程中，绝不会进入负坐标区域。
• 不能连续使用同一个跳跃距离分别往相反方向跳跃。

一个满足条件的操作序列的代价定义为按照该序列移动过程中到达过的最大坐标值。请你求出所有符合条件的操作序列中，代价的最小值。在本题的约束条件下，始终存在满足条件的操作序列。

需要你对 $T$ 组测试数据分别解答。

输入采用标准输入，格式如下：

$T$

$N_1 \quad A_{1,1} \quad A_{1,2} \quad \cdots \quad A_{1,N_1}$

$N_2 \quad A_{2,1} \quad A_{2,2} \quad \cdots \quad A_{2, N_2}$

$\vdots$

$N_T \quad A_{T,1} \quad A_{T,2} \quad \cdots \quad A_{T, N_T}$

对于每组测试数据，输出一行答案。

样例解释 1

以第一组样例为例。跳跃过程 $0 \to 2 \to 4 \to 1 \to 3 \to 0$ 满足所有条件，此时代价为 $4$。不存在代价小于 $4$ 的合法操作序列，所以答案为 $4$。

约束条件

• $1 \leq T \leq 125000$
• $2 \leq N \leq 250000$
• $1 \leq A_1 < A_2 < \cdots < A_N \leq 10^{18}$
• 所有测试数据中 $N$ 的总和不超过 $250000$。
• 所有输入值均为整数。

由 ChatGPT 5 翻译