AT_agc073_b [AGC073B] Cyclic Jump

長さ $ N $ の正整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます． あなたは今，数直線上の座標 $ 0 $ の位置に立っており，今から以下の操作を好きな回数行います． - $ A $ の好きな要素 $ A_i $ を自由に選ぶ．また，正負のうち好きな方向を選ぶ． そして，選んだ方向に距離 $ A_i $ だけジャンプする． あなたは以下の条件を満たす操作列に興味があります． - 操作を $ 1 $ 回以上行い，最終的に座標 $ 0 $ に戻ってくる． - 途中で座標が負の領域に入らない． - 連続して同じ距離かつ異なる方向にジャンプすることがない． 条件を満たす操作列の**コスト**を，その操作列に従って動いた際に訪れる座標の最大値とします． 条件を満たす操作列のコストとしてあり得る最小値を求めてください． なおこの問題の制約より，条件を満たす操作列は必ず存在します． $ 1 $ つの入力につき， $ T $ 個のテストケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

各テストケースに対し，答えを出力せよ．

### Sample Explanation 1 $ 1 $ つ目のテストケースについて考えます． 座標 $ 0 \to 2 \to 4 \to 1 \to 3 \to 0 $ という移動方法は条件を満たし，このときのコストは $ 4 $ です． コストが $ 4 $ 未満になる操作列は存在しないため，答えは $ 4 $ になります． ### Constraints - $ 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 $ を超えない - 入力はすべて整数