Busy Beaver adore passer ses après-midi au Banana Lounge du MIT. Il décide d'aider à empiler des boîtes de bananes ! Il doit collecter l'inventaire de $N$ pièces consécutives, disposées sur une seule rangée et numérotées de $1$ à $N$ de gauche à droite. En raison de l'architecture particulière des bâtiments du MIT, chaque pièce $i$ a une hauteur de plafond spécifique, $h_i$.

Busy Beaver doit sélectionner une pièce $k$ ($1 \le k \le N$) pour servir de hub principal. Ensuite, $N$ de ses amis, un dans chaque pièce, transportent chacun une pile verticale de boîtes de bananes depuis leur pièce de départ $i$ directement vers la pièce hub $k$. Comme ils doivent marcher en ligne droite, le nombre maximum de boîtes qu'ils peuvent transporter est limité par la hauteur minimale sur leur chemin.

Formellement, le nombre de boîtes de bananes livrées par l'ami partant de la pièce $i$ vers la pièce hub $k$ est :

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

Le nombre total de boîtes de bananes rassemblées au hub est la somme des boîtes livrées par les $N$ amis, qui est :

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

Heureusement, Busy Beaver a un ami au service des installations du MIT. Avant que les amis ne commencent à transporter les boîtes, il peut demander de rénover au plus une pièce (qui ne peut pas être la pièce hub choisie $k$) pour changer sa hauteur de plafond $h_i$ à n'importe quelle valeur.

Quel est le nombre total maximum de boîtes de bananes que Busy Beaver peut rassembler au hub principal après avoir choisi l'emplacement optimal du hub $k$ et effectué au plus une rénovation de plafond ?

Entrée

La première ligne contient un entier unique $T$ ($1 \le T \le 10^5$) — le nombre de cas de test.

La première ligne de chaque cas de test contient un entier unique $N$ ($2 \le N \le 10^6$).

La ligne suivante de chaque cas de test contient $N$ entiers séparés par des espaces $h_1, h_2, \dots, h_N$ ($1 \le h_i \le 10^9$).

La somme de $N$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez une ligne contenant un entier : la réponse pour le cas de test.

Barème

Il y a deux sous-tâches pour ce problème :

• (30 points) : La somme de $N$ sur tous les cas de test ne dépasse pas $3 \cdot 10^3$.
• (70 points) : Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

32
50

Remarque

Dans le premier cas de test, la meilleure option est de choisir le hub $k = 2$ et de rénover $h_3$ à au moins $10$, permettant aux trois amis du milieu de transporter chacun $10$, pour un total de $32$.

Dans le second cas de test, aucune rénovation ne peut augmenter le nombre de boîtes de bananes, donc la réponse est $50$.