AT_tupc2024_p Adjacent Reset

長さ $ N $ の正整数列 $ A = (A_1,A_2,\dots,A_N) $ が与えられます。 $ A $ に対して以下の操作を $ 0 $ 回以上繰り返すことができます。 - 整数 $ i \ (1 \le i \le N-1) $ を $ 1 $ つ選び、 $ A_i, A_{i+1} $ をどちらも $ 0 $ に置き換える。この操作にはコストが $ \max(A_i,A_{i+1}) $ かかる。 $ A $ の全ての要素を $ 0 $ にするために必要なコストの和の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。

### Universal Cup 参加者へ この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。 ### Sample Explanation 1 $ 1 $ つ目のテストケースについて、例えば以下のように $ 3 $ 回の操作を行うことができます。 - $ A=(2,6,7,3) $ に対して $ i = 2 $ として操作を行い、 $ A=(2,0,0,3) $ となる。コストが $ 7 $ かかる。 - $ A=(2,0,0,3) $ に対して $ i = 1 $ として操作を行い、 $ A=(0,0,0,3) $ となる。コストが $ 2 $ かかる。 - $ A=(0,0,0,3) $ に対して $ i = 3 $ として操作を行い、 $ A=(0,0,0,0) $ となる。コストが $ 3 $ かかる。 かかったコストの和は $ 7+2+3=12 $ です。 $ A=(0,0,0,0) $ とするためにかかるコストの和はこれより小さくできないため、 $ 12 $ が答えになります。 ### Constraints - $ 1 \le T \le 10^5 $ - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \le A_i \le 10^9 $ - $ 1 $ つの入力ファイルに含まれる $ N $ の総和は $ 2\times 10^5 $ 以下 - 入力は全て整数