Busy Beaver uwielbia spędzać popołudnia w Banana Lounge na MIT. Postanowił pomóc w układaniu pudełek z bananami! Musi zebrać zapasy z $N$ kolejnych pokoi, ustawionych w jednym rzędzie i ponumerowanych od $1$ do $N$ od lewej do prawej. Ze względu na specyficzną architekturę budynków MIT, każdy pokój $i$ ma określoną wysokość prześwitu sufitu, $h_i$.

Busy Beaver musi wybrać jeden pokój $k$ ($1 \le k \le N$), który będzie pełnił funkcję Głównego Węzła (Main Hub). Następnie $N$ jego przyjaciół, po jednym z każdego pokoju, przenosi pionowy stos pudełek z bananami ze swojego pokoju startowego $i$ bezpośrednio do pokoju węzłowego $k$. Ponieważ muszą poruszać się w linii prostej, maksymalna liczba pudełek, które mogą przenieść, jest ograniczona przez minimalny prześwit na ich drodze.

Formalnie, liczba pudełek z bananami dostarczonych przez przyjaciela startującego z pokoju $i$ do pokoju węzłowego $k$ wynosi:

• $\min(h_i, h_{i+1}, \dots, h_k)$ jeśli $i \le k$.
• $\min(h_k, h_{k+1}, \dots, h_i)$ jeśli $i > k$.

Całkowita liczba pudełek z bananami zgromadzonych w węźle jest sumą pudełek dostarczonych przez wszystkich $N$ przyjaciół, co wynosi:

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

Na szczęście Busy Beaver ma przyjaciela w dziale technicznym MIT. Zanim przyjaciele zaczną przenosić pudełka, może on poprosić o wyremontowanie co najwyżej jednego pokoju (którym nie może być wybrany pokój węzłowy $k$), aby zmienić jego wysokość prześwitu $h_i$ na dowolną wartość.

Jaka jest maksymalna całkowita liczba pudełek z bananami, jaką Busy Beaver może zgromadzić w Głównym Węźle po wybraniu optymalnej lokalizacji węzła $k$ i wykonaniu co najwyżej jednego remontu sufitu?

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T \le 10^5$) — liczbę zestawów danych. Pierwsza linia każdego zestawu danych zawiera pojedynczą liczbę całkowitą $N$ ($2 \le N \le 10^6$). Następna linia każdego zestawu danych zawiera $N$ liczb całkowitych oddzielonych spacjami $h_1, h_2, \dots, h_N$ ($1 \le h_i \le 10^9$). Suma $N$ we wszystkich zestawach danych nie przekracza $10^6$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii jedną liczbę całkowitą: odpowiedź dla danego zestawu.

Podzadania

Istnieją dwa podzadania dla tego problemu:

• (30 punktów): Suma $N$ we wszystkich zestawach danych nie przekracza $3 \cdot 10^3$.
• (70 punktów): Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

32
50

Uwagi

W pierwszym przypadku testowym najlepszą opcją jest wybór węzła $k = 2$ i wyremontowanie $h_3$ do co najmniej $10$, co pozwala trzem środkowym przyjaciołom przenieść po $10$ pudełek, co daje łącznie $32$.

W drugim przypadku testowym żaden remont nie może zwiększyć liczby pudełek z bananami, więc odpowiedzią jest $50$.