Cyclic Jump

AtCoder

IDagc073_b

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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

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$.

API Response (JSON)

{
  "problem": {
    "name": "Cyclic Jump",
    "description": {
      "content": "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 ti",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc073_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a length-$N$ positive integer sequence $A = (A_1, A_2, \\ldots, A_N)$.\nYou are now standing at coordinate $0$ on the number line, and will perform the following operation any number of ti...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments