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 翻译