Busy Beaver は MIT の Banana Lounge で午後を過ごすのが大好きです。彼はバナナの箱を積み上げる手伝いをすることにしました！彼は、$N$ 個の連続する部屋にまたがる在庫を集める必要があります。これらの部屋は一列に並んでおり、左から右へ $1$ から $N$ まで番号が振られています。MIT の建物の独特な建築構造のため、各部屋 $i$ には特定の天井の高さ $h_i$ があります。

Busy Beaver は、メインハブとして $1$ つの部屋 $k$ ($1 \le k \le N$) を選ぶ必要があります。その後、各部屋に $1$ 人ずついる $N$ 人の友人が、それぞれ自分の出発する部屋 $i$ からハブである部屋 $k$ まで、バナナの箱を垂直に積み上げて運びます。彼らは一直線に歩かなければならないため、運べる箱の最大数は経路上の最小の高さによって制限されます。

形式的には、部屋 $i$ から出発してハブである部屋 $k$ に届ける友人が運ぶバナナの箱の数は以下の通りです。

• $i \le k$ の場合: $\min(h_i, h_{i+1}, \dots, h_k)$
• $i > k$ の場合: $\min(h_k, h_{k+1}, \dots, h_i)$

ハブに集められるバナナの箱の総数は、すべての $N$ 人の友人が運んだ箱の合計であり、以下の式で表されます。

$$\sum_{i=1}^{k-1} \min(h_i, \dots, h_k) + h_k + \sum_{i=k+1}^{N} \min(h_k, \dots, h_i)$$

幸いなことに、Busy Beaver には MIT 施設部に友人がいます。友人たちが箱を運び始める前に、彼は最大で $1$ つの部屋（選んだハブである部屋 $k$ は不可）を改修し、その天井の高さ $h_i$ を任意の値に変更するよう依頼できます。

最適なハブの場所 $k$ を選択し、最大で $1$ つの天井の改修を行った後、Busy Beaver がメインハブに集めることができるバナナの箱の総数の最大値はいくつでしょうか？

入力

入力の最初の行には、テストケースの数 $T$ ($1 \le T \le 10^5$) が含まれます。 各テストケースの最初の行には、整数 $N$ ($2 \le N \le 10^6$) が含まれます。 各テストケースの次の行には、$N$ 個のスペース区切りの整数 $h_1, h_2, \dots, h_N$ ($1 \le h_i \le 10^9$) が含まれます。 すべてのテストケースにおける $N$ の合計は $10^6$ を超えません。

出力

各テストケースについて、そのテストケースの答えである整数を $1$ 行に出力してください。

小課題

この問題には $2$ つの小課題があります。

• ($30$ 点): すべてのテストケースにおける $N$ の合計は $3 \cdot 10^3$ を超えません。
• ($70$ 点): 追加の制約はありません。

入出力例

入力 1

2
5
1 10 1 10 1
5
10 10 10 10 10

出力 1

32
50

注記

最初のサンプルケースでは、ハブ $k = 2$ を選択し、$h_3$ を $10$ 以上に改修するのが最善の選択肢であり、これにより中央の $3$ 人の友人が全員 $10$ 個運べるようになり、合計で $32$ となります。 $2$ 番目のサンプルケースでは、改修を行ってもバナナの箱の数は増えないため、答えは $50$ となります。