Busy Beaver любит проводить свои дни в Banana Lounge в MIT. Он решил помочь со складированием коробок с бананами! Ему нужно собрать инвентарь из $N$ последовательных комнат, расположенных в один ряд и пронумерованных от $1$ до $N$ слева направо. Из-за необычной архитектуры зданий MIT каждая комната $i$ имеет определенную высоту потолка $h_i$.

Busy Beaver должен выбрать одну комнату $k$ ($1 \le k \le N$), которая станет главным хабом. Затем $N$ его друзей, по одному из каждой комнаты, несут вертикальную стопку коробок с бананами из своей начальной комнаты $i$ прямо в хаб $k$. Поскольку они должны идти по прямой линии, максимальное количество коробок, которое они могут нести, ограничено минимальной высотой потолка на их пути.

Формально, количество коробок с бананами, доставленных другом, начинающим путь из комнаты $i$ в хаб $k$, равно:

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

Общее количество коробок с бананами, собранных в хабе, равно сумме коробок, доставленных всеми $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$ на любое значение.

Каково максимальное общее количество коробок с бананами, которое Busy Beaver может собрать в главном хабе после выбора оптимального расположения хаба $k$ и выполнения не более одного ремонта потолка?

Входные данные

Первая строка содержит единственное целое число $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

32
50

Примечание

В первом примере оптимальным решением является выбор хаба $k = 2$ и ремонт $h_3$ до значения не менее $10$, что позволит трем друзьям из середины нести по $10$ коробок, что в сумме дает $32$.

Во втором примере никакой ремонт не может увеличить количество коробок с бананами, поэтому ответ равен $50$.