CF1534B.Histogram Ugliness

Little Dormi received a histogram with $n$ bars of height $a_1, a_2, \ldots, a_n$ for Christmas. However, the more he played with his new histogram, the more he realized its imperfections, so today he wanted to modify it to his liking.

To modify the histogram, Little Dormi is able to perform the following operation an arbitrary number of times:

• Select an index $i$ ($1 \le i \le n$) where $a_i \gt 0$, and assign $a_i := a_i-1$.

Little Dormi defines the ugliness score of his histogram (after performing some number of operations) as the sum of the vertical length of its outline and the number of operations he performed on it. And to make the histogram as perfect as possible, he would like to minimize the ugliness score after modifying it with some number of operations.

However, as his histogram is very large, Little Dormi is having trouble minimizing the ugliness score, so as Little Dormi's older brother, help him find the minimal ugliness.

Consider the following example where the histogram has $4$ columns of heights $4,8,9,6$:

The blue region represents the histogram, and the red lines represent the vertical portion of the outline. Currently, the vertical length of the outline is $4+4+1+3+6 = 18$, so if Little Dormi does not modify the histogram at all, the ugliness would be $18$.

However, Little Dormi can apply the operation once on column $2$ and twice on column $3$, resulting in a histogram with heights $4,7,7,6$:

Now, as the total vertical length of the outline (red lines) is $4+3+1+6=14$, the ugliness is $14+3=17$ dollars. It can be proven that this is optimal.

小 Dormi 在圣诞节收到了一个包含 $n$ 根柱子的直方图，各柱高度分别为 $a_1, a_2, \ldots, a_n$。然而，他玩得越久，就越意识到这个直方图的不完美之处；因此，今天他想按自己的喜好对它进行修改。

为修改该直方图，小 Dormi 可以任意次数地执行以下操作：

• 选择一个下标 $i$（$1 \le i \le n$），满足 $a_i \gt 0$，并令 $a_i := a_i-1$。

小 Dormi 将其直方图（在执行若干次操作后）的“丑陋度”定义为：其轮廓线中竖直方向的总长度与所执行操作次数之和。为了使直方图尽可能“完美”，他希望在执行若干次操作后，使丑陋度最小化。

然而，由于他的直方图非常大，小 Dormi 难以自行求出最小丑陋度；因此，请作为小 Dormi 的哥哥，帮他找出该最小丑陋度。

考虑如下例子：直方图有 $4$ 列，高度分别为 $4,8,9,6$：

蓝色区域表示直方图本身，红色线条表示其轮廓线的竖直部分。当前，轮廓线的竖直总长度为 $4+4+1+3+6 = 18$，因此若小 Dormi 完全不修改直方图，丑陋度即为 $18$。

然而，小 Dormi 可在第 $2$ 列执行一次操作、在第 $3$ 列执行两次操作，从而得到新的高度序列 $4,7,7,6$：

此时，轮廓线的竖直总长度（红色线条）为 $4+3+1+6=14$，故丑陋度为 $14+3=17$。可以证明，这是最优解。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 4 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $4 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case output one integer, the minimal ugliness Little Dormi can achieve with the histogram in that test case.

对于每个测试用例，输出一个整数，表示 Little Dormi 在该测试用例的直方图中所能达到的最小丑陋度。

Example $1$ is the example described in the statement.

The initial histogram for example $2$ is given below:

The ugliness is currently $2+1+6+3+4=16$.

By applying the operation once on column $1$, six times on column $3$, and three times on column $4$, we can end up with a histogram with heights $1,1,1,1,0,0$:

The vertical length of the outline is now $1+1=2$ and Little Dormi made $1+6+3=10$ operations, so the final ugliness is $2+10=12$, which can be proven to be optimal.

示例 $1$ 即题面中所描述的示例。

示例 $2$ 的初始直方图如下所示：

当前丑陋度为 $2+1+6+3+4=16$。

通过对第 $1$ 列执行一次操作、第 $3$ 列执行六次操作、第 $4$ 列执行三次操作，我们可以得到一个高度序列为 $1,1,1,1,0,0$ 的直方图：

此时轮廓的垂直长度为 $1+1=2$，且 Little Dormi 共执行了 $1+6+3=10$ 次操作，因此最终丑陋度为 $2+10=12$，该值可被证明是最优的。