Description

wyl学长收到了一个直方图作为礼物，直方图包含n列，高度依次为a​1​,a2​,...,an​。然而，他越是玩弄他的直方图，他越是意识到它的不完美，所以今天他想要修改它，以满足他的喜好。

为了修改直方图，wyl学长可以执行任意次数的如下操作:

选择一个位置 i (1≤ i ≤ n),其中 $a_i$ > 0，然后修改第i列的高度$a​_i = a_i -1$。

wyl学长把他的直方图的丑陋指数(在执行了一些操作之后)定义为它的轮廓的垂直长度和他在上面执行的操作的次数之和。为了使直方图尽可能完美，他希望通过数次上述操作来修改直方图，从而最小化它的丑陋指数。

然而，由于他的直方图非常大，wyl学长很难把丑陋指数最小化，所以他向聪明的你求助，请你帮助他找到最小化的丑陋指数。

考虑下面的例子，其中直方图有4列，高度为4,8,9,6

蓝色区域代表直方图，红色线条代表轮廓的垂直部分。目前，轮廓的垂直长度是4 + 4 + 1 + 3 + 6 = 18，所以如果wyl学长不修改直方图，那么丑陋指数就是18。

然而，wyl学长可以在第2列上进行一次上述操作，在第3列上进行两次上述操作，结果得到一个高度为4,7,7,6的直方图:

现在，由于轮廓的总垂直长度(红线)是4 + 3 + 1 + 6 = 14，所以丑陋指数是14 + 3 = 17。可以证明这是最优的。

Input Format

每个测试包含多个测试用例。第一行输入一个测试用例数​t​(1≤ t ≤10​^4​) 。测试用例的描述如下:

每个测试用例的第一行包含一个整数​n​(1≤ n ≤4×10​^5^​)。

每个测试用例的第二行包含n个整数 a​1​，a​2​，... ，a​n​(0≤ ai ​≤10​^9​)。

可以保证所有测试案例的n之和不超过4×10​^5​。

Output Format

对于每个测试用例输出一个整数，表示wyl学长可以用该测试用例的直方图实现的最小丑陋指数。

2
4
4 8 9 6
6
2 1 7 4 0 0​

17
12​

Hint

例1是问题中描述的例子。

例2的初始直方图如下:

丑陋指数现在是2 + 1 + 6 + 3 + 4 = 16。

通过在列1上操作一次，在列3上操作六次，在列4上操作三次，我们可以得到一个高度为1,1,1,1,0,0的直方图:

现在轮廓的垂直长度是1 + 1 = 2，wyl学长做了1 + 6 + 3 = 10次操作，所以最终的丑陋指数是2 + 10 = 12，可以证明是最佳的。

Source

思维 CF1100