Array Covering

题号：NC301430
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$ ，其中第 $i$ 个数的值为 $a_i$ 。

$\hspace{15pt}$ 小苯希望数组中所有数字的总和尽可能大，为此他可以做任意次如下操作：

$\hspace{23pt}\bullet\,$ 选择一对下标 $l, r\left(1 \leqq l < r \leq n\right)$ ，接着将 $(l,r)$ 区间（注意是开区间）内的所有数都变为区间端点值的较大者。

$\hspace{30pt}$ 形式化地，对所有 $j\left(l<j<r\right)$ ，均执行： $a_j:=\max(a_l,a_r)$ （其中 $:=$ 表示赋值操作）。

$\hspace{15pt}$ 你的任务就是求出数组总和的最大值。

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个正整数 ，表示数组  的长度。
第二行输入  个正整数 ，表示最初时所有数字的值。

除此之外，保证单个测试文件的  之和不超过 。

对于每一组测试数据，新起一行输出一个正整数，表示在可以进行任意次操作的情况下，所有数字之和的最大值。

示例1

复制

复制

15
4

对于第一组测试数据，可以选择  操作一次，操作完后数组为 ，求和为 。我们可以证明，无法通过其他操作使得总和更大。