CF2185B.Prefix Max

You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$.

The value of an array is the sum of the maximums of each prefix of the array. More formally, the value of an array $a$ is $\sum_{i=1} ^{n} \operatorname{max}(a_1, \ldots, a_i)$. For example, the value of the array [$1, 2, 1$] is $\operatorname{max}(1) + \operatorname{max}(1, 2) + \operatorname{max}(1, 2, 1) = 1 + 2 + 2 = 5$.

You can choose two indices $i$ and $j$ and swap elements $a_i$ and $a_j$; this operation can be applied at most one time.

Find the maximum possible value of the array $a$ after at most one operation.

给你一个包含 $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$ 可能达到的最大值。

The first line of the input contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 50$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^4$) — the array $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$。

For each test case, output the maximum possible value of the array $a$ after the swap has been performed.

对于每个测试用例，输出执行交换操作后数组 $a$ 的最大可能值。

For the first test case, we can swap $a_1$ with $a_4$ to get the array [$5, 1, 4, 2, 3$], which has a value of $\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$.

For the second test case, the current value of the array is $\operatorname{max}(5) + \operatorname{max}(5, 1) = 10$. If we were to swap $a_1$ and $a_2$, $a$ would be equal to [$1, 5$], which has a value of $\operatorname{max}(1) + \operatorname{max}(1, 5) = 6$, meaning the best option is to not perform a swap.

对于第一个测试用例，我们可以交换 $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$，因此最优选择是不执行任何交换。