题目描述

给定一个长度为 $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$ 能获得的最大价值。

说明/提示

对于第一个测试用例，我们可以将 $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$，因此最优方案是不进行任何交换操作。

由 ChatGPT 5 翻译

样例

4
5
2 1 4 5 3
2
5 1
3
3 2 1
2
6 7

25
10
9
14