B. Префиксный максимум
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Значение массива — это сумма максимумов каждого префикса массива. Более формально, значение массива $$$a$$$ равно $$$\sum_{i=1} ^{n} \operatorname{max}(a_1, \ldots, a_i)$$$. Например, значение массива [$$$1, 2, 1$$$] равно $$$\operatorname{max}(1) + \operatorname{max}(1, 2) + \operatorname{max}(1, 2, 1) = 1 + 2 + 2 = 5$$$.

Вы можете выбрать два индекса $$$i$$$ и $$$j$$$ и поменять местами элементы $$$a_i$$$ и $$$a_j$$$; эта операция может быть выполнена не более одного раза.

Найдите максимальное возможное значение массива $$$a$$$ после выполнения не более одной операции.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 50$$$) — длину массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) — массив $$$a$$$.

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

Для каждого набора входных данных выведите максимальное возможное значение массива $$$a$$$ после выполнения обмена.

Пример
Входные данные
4
5
2 1 4 5 3
2
5 1
3
3 2 1
2
6 7
Выходные данные
25
10
9
14
Примечание

Для первого набора входных данных мы можем поменять местами $$$a_1$$$ с $$$a_4$$$, чтобы получить массив [$$$5, 1, 4, 2, 3$$$], который имеет значение $$$\operatorname{max}(5) + \operatorname{max}(5, 1) + \operatorname{max}(5, 1, 4) + \operatorname{max}(5, 1, 4, 2) + \operatorname{max}(5, 1, 4, 2, 3) = 25$$$.

Для второго набора входных данных текущее значение массива равно $$$\operatorname{max}(5) + \operatorname{max}(5, 1) = 10$$$. Если мы поменяем местами $$$a_1$$$ и $$$a_2$$$, то $$$a$$$ будет равно [$$$1, 5$$$], что имеет значение $$$\operatorname{max}(1) + \operatorname{max}(1, 5) = 6$$$, что означает, что лучший вариант — не выполнять обмен.