{"raw_statement":[{"iden":"problem statement","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 times:\n\n*   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.\n\nYou are interested in operation sequences that satisfy the following conditions:\n\n*   Perform the operation at least once and finally return to coordinate $0$.\n*   Never enter the negative region during the process.\n*   Never jump consecutively the same distance in different directions.\n\nThe **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.\nSolve $T$ test cases for one input."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 125000$\n*   $2 \\leq N \\leq 250000$\n*   $1 \\leq A_1 < A_2 < \\cdots < A_N \\leq 10^{18}$\n*   The sum of $N$ in one input does not exceed $250000$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"5\n2\n2 3\n2\n3 6\n3\n3 5 6\n2\n999999999999999999 1000000000000000000\n3\n999999999999999998 999999999999999999 1000000000000000000"},{"iden":"sample output 1","content":"4\n6\n6\n1999999999999999998\n1000000000000000000\n\nConsider 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$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}