给你一个 $$$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$$$ 的最大可能值。
示例
输入复制
452 1 4 5 325 133 2 126 7
输出复制
2510914
注意
对于第一个测试用例,我们可以将 $$$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$$$,这意味着最好的选择是不执行交换。