Busy Beaver 很喜歡在 MIT 的 Banana Lounge 度過他的下午。他決定幫忙堆疊香蕉箱！他需要在 $N$ 個連續的房間中收集庫存，這些房間排成一列，並從左到右編號為 $1$ 到 $N$。由於 MIT 建築的獨特結構，每個房間 $i$ 都有一個特定的天花板淨空高度 $h_i$。

Busy Beaver 需要選擇一個房間 $k$ ($1 \le k \le N$) 作為中心樞紐（Main Hub）。接著，他的 $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 設施部門有一位朋友。在朋友們開始運送箱子之前，他可以請求翻修至多一個房間（不能是已選定的樞紐房間 $k$），將其淨空高度 $h_i$ 改為任意值。

在選擇最佳樞紐位置 $k$ 並進行至多一次天花板翻修後，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$。

輸出格式

對於每組測試資料，輸出一行包含一個整數，代表該測試資料的答案。

子任務

本題共有兩個子任務：

• (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$，這使得中間的三位朋友都能攜帶 $10$ 個箱子，總計為 $32$。 在第二個範例中，沒有任何翻修可以增加香蕉箱的數量，因此答案為 $50$。