AT_agc073_b [AGC073B] Cyclic Jump

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.

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 $

For each test case, output the answer.

### Sample Explanation 1 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 $ . ### 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.