Universal Cup 参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

長さ 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 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 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 以下
• 入力は全て整数

入力例 1

4
4
2 6 7 3
2
1 1000000000
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
8
123 4567 8912 34 56789 12345 6789 1

出力例 1

12
1000000000
10
72647

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 が答えになります。