← 返回题目列表

AtCoder · agc073_b

B. 循环跳转

中文机器翻译题面 查看原题

分数: 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.