B - Cyclic Jump Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1000 点

問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます．

あなたは今，数直線上の座標 0 の位置に立っており，今から以下の操作を好きな回数行います．

  • A の好きな要素 A_i を自由に選ぶ．また，正負のうち好きな方向を選ぶ． そして，選んだ方向に距離 A_i だけジャンプする．

あなたは以下の条件を満たす操作列に興味があります．

  • 操作を 1 回以上行い，最終的に座標 0 に戻ってくる．
  • 途中で座標が負の領域に入らない．
  • 連続して同じ距離かつ異なる方向にジャンプすることがない．

条件を満たす操作列のコストを，その操作列に従って動いた際に訪れる座標の最大値とします． 条件を満たす操作列のコストとしてあり得る最小値を求めてください． なおこの問題の制約より，条件を満たす操作列は必ず存在します．

1 つの入力につき，T 個のテストケースを解いてください．

制約

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 250000
  • 1 \leq A_1 < A_2 < \cdots < A_N \leq 10^{18}
  • 1 つの入力における 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

1 つ目のテストケースについて考えます． 座標 0 \to 2 \to 4 \to 1 \to 3 \to 0 という移動方法は条件を満たし，このときのコストは 4 です． コストが 4 未満になる操作列は存在しないため，答えは 4 になります．

Score : 1000 points

Problem Statement

You are given a length-N positive integer sequence A = (A_1, A_2, \ldots, A_N).

You are now standing at coordinate 0 on the number line, and will perform the following operation any number of times:

  • Choose any element A_i from A freely. Also, choose either positive or negative direction freely. Then, jump distance A_i in the chosen direction.

You are interested in operation sequences that satisfy the following conditions:

  • Perform the operation at least once and finally return to coordinate 0.
  • Never enter the negative region during the process.
  • Never jump consecutively the same distance in different directions.

The cost of an operation sequence satisfying the conditions is the maximum value among the coordinates visited when moving according to that operation sequence. Find the minimum possible cost among operation sequences satisfying the conditions. Under the constraints of this problem, an operation sequence satisfying the conditions always exists.

Solve T test cases for one input.

Constraints

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 250000
  • 1 \leq A_1 < A_2 < \cdots < A_N \leq 10^{18}
  • The sum of N in one input does not exceed 250000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N
A_1 A_2 \cdots A_N

Output

For each test case, output the answer.

Sample Input 1

5
2
2 3
2
3 6
3
3 5 6
2
999999999999999999 1000000000000000000
3
999999999999999998 999999999999999999 1000000000000000000

Sample Output 1

4
6
6
1999999999999999998
1000000000000000000

Consider the first test case. The movement method 0 \to 2 \to 4 \to 1 \to 3 \to 0 satisfies the conditions, and the cost in this case is 4. There is no operation sequence with cost less than 4, so the answer is 4.