小多米在圣诞节收到了一张直方图,其中包含 $$$n$$$ 条形,高度为 $$$a_1、a_2、\ldots、a_n$$$。然而,他对新直方图玩得越多,就越意识到它的缺陷,所以今天他想根据自己的喜好修改它。
要修改直方图,Little Dormi 可以执行任意次数的以下操作:
- 选择索引 $$$i$$$ ($$$1 \le i \le n$$$),其中 $$$a_i>0$$$,并分配 $$$a_i := a_i-1$$$。
Little Dormi 将他的直方图(执行一定次数的操作后)的丑陋分数定义为其轮廓的垂直长度与他对其执行的操作次数之和。为了使直方图尽可能完美,他希望通过一些操作修改后将丑陋分数最小化。
然而,由于他的直方图非常大,Little Dormi 很难最小化丑陋分数,所以作为 Little Dormi 的哥哥,帮助他找到最小的丑陋分数。
考虑以下示例,其中直方图具有高度为 $$$4,8,9,6$$$ 的 $$$4$$$ 列:
蓝色区域代表直方图,红线代表轮廓的垂直部分。目前,轮廓的垂直长度为$$$4+4+1+3+6 = 18$$$,所以如果Little Dormi根本不修改直方图,丑陋的程度将是$$$18$$$。
但是,Little Dormi 可以在 $$$2$$$ 列上应用一次操作,在 $$$3$$$ 列上应用两次操作,从而得到高度为 $$$4,7,7,6$$$ 的直方图:
现在,由于轮廓(红线)的总垂直长度为 $$$4+3+1+6=14$$$,因此丑陋程度为 $$$14+3=17$$$ 美元。可以证明这是最优的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$4 \cdot 10^5$$$。
输出
对于每个输出一个整数的测试用例,Little Dormi 通过该测试用例中的直方图可以实现的最小丑陋。
示例
输入 #1
2 4 4 8 9 6 6 2 1 7 4 0 0
输出 #1
17 12
注意
示例 $$$1$$$ 是语句中描述的示例。
例如 $$$2$$$ 的初始直方图如下:
目前的丑陋程度为$$$2+1+6+3+4=16$$$。
通过对 $$$1$$$ 列应用一次操作,对 $$$3$$$ 列应用操作六次,对 $$$4$$$ 列应用操作三次,我们最终可以得到高度为 $$$1,1,1,1,0,0$$$ 的直方图:
现在轮廓的垂直长度为$$$1+1=2$$$,小多米进行了$$$1+6+3=10$$$操作,所以最终的丑数为$$$2+10=12$$$,可以证明是最优的。