分数: 1000 点
问题陈述
给你一个长度-N 正整数序列 A = (A_1, A_2, \ldots, A_N).
你现在正站在坐标处 0 在数轴上,并将执行以下操作任意次:
- 选择任意元素 A_i 来自 A 自由。另外,可以自由选择正向或负向。 然后,跳跃距离 A_i 沿所选方向。
您对满足以下条件的操作序列感兴趣:
- 至少执行一次操作,最终返回坐标 0.
- 在此过程中切勿进入负区域。
- 切勿在不同方向连续跳跃相同的距离。 满足条件的操作序列的
的 成本 这种排列的 是按照该操作序列移动时所访问的坐标中的最大值。 找出满足条件的操作序列中可能的最小成本。 在该问题的约束下,满足条件的操作序列总是存在的。
解决 T 一个输入的测试用例。
约束
- 1 \leq T \leq 125000
- 2 \leq N \leq 250000
- 1 \leq A_1 < A_2 < \cdots < A_N \leq 10^{18}
- 总和 N 一次输入不超过 250000.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个测试用例均按以下格式给出:
N A_1 A_2 \cdots A_N
输出
对于每个测试用例,输出答案。
示例输入 1
5 2 2 3 2 3 6 3 3 5 6 2 999999999999999999 1000000000000000000 3 999999999999999998 999999999999999999 1000000000000000000
示例输出 1
4 6 6 1999999999999999998 1000000000000000000
考虑第一个测试用例。 运动方法 0 \to 2 \to 4 \to 1 \to 3 \to 0 满足条件,此时的成本为 4。 不存在成本小于的操作序列 4,所以答案是 4.