CF1706C.Qpwoeirut And The City

Qpwoeirut has taken up architecture and ambitiously decided to remodel his city.

Qpwoeirut's city can be described as a row of $n$ buildings, the $i$-th ($1 \le i \le n$) of which is $h_i$ floors high. You can assume that the height of every floor in this problem is equal. Therefore, building $i$ is taller than the building $j$ if and only if the number of floors $h_i$ in building $i$ is larger than the number of floors $h_j$ in building $j$.

Building $i$ is cool if it is taller than both building $i-1$ and building $i+1$ (and both of them exist). Note that neither the $1$-st nor the $n$-th building can be cool.

To remodel the city, Qpwoeirut needs to maximize the number of cool buildings. To do this, Qpwoeirut can build additional floors on top of any of the buildings to make them taller. Note that he cannot remove already existing floors.

Since building new floors is expensive, Qpwoeirut wants to minimize the number of floors he builds. Find the minimum number of floors Qpwoeirut needs to build in order to maximize the number of cool buildings.

Qpwoeirut 开始学习建筑学，并雄心勃勃地决定改造他的城市。

Qpwoeirut 的城市可以被描述为一排 $n$ 座建筑，其中第 $i$ 座（$1 \le i \le n$）建筑高 $h_i$ 层。你可以假设本题中每层楼的高度均相等。因此，当且仅当第 $i$ 座建筑的楼层数 $h_i$ 大于第 $j$ 座建筑的楼层数 $h_j$ 时，第 $i$ 座建筑才比第 $j$ 座建筑更高。

若第 $i$ 座建筑比其左右相邻的两座建筑（即第 $i-1$ 座和第 $i+1$ 座建筑）都更高（且这两座相邻建筑均存在），则称第 $i$ 座建筑是“酷”的。注意：第 $1$ 座和第 $n$ 座建筑不可能是“酷”的。

为了改造城市，Qpwoeirut 需要使“酷”建筑的数量最大化。为此，他可以在任意建筑顶部增建若干楼层，使其变高（但不能拆除已有的楼层）。

由于增建楼层成本高昂，Qpwoeirut 希望最小化所增建的楼层数。请找出在使“酷”建筑数量最大化的前提下，Qpwoeirut 所需增建的最少楼层数。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($3 \le n \le 10^5$) — the number of buildings in Qpwoeirut's city.

The second line of each test case contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$) — the number of floors in each of the buildings of the city.

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 10^5$）—— Qpwoeirut 所在城市中建筑物的数量。

每个测试用例的第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$1 \le h_i \le 10^9$）—— 城市中每栋建筑物的楼层数。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print a single integer — the minimum number of additional floors Qpwoeirut needs to build in order to maximize the number of cool buildings.

对于每个测试用例，输出一个整数——Qpwoeirut 为使“酷建筑”的数量最大化而需要额外建造的最少楼层数。

In the first test case, it is optimal for Qpwoeirut to make the second building cool by building $2$ additional floors on top of it, making it taller than both of its adjacent buildings. The final heights of buildings will be $[2, \underline{3}, 2]$.

In the second test case, the number of cool buildings is already maximized, so Qpwoeirut does not need to do anything.

In the third test case, it is optimal for Qpwoeirut to make the third and fifth buildings cool by building $2$ additional floors onto the third building and $1$ additional floor onto the fifth building. The final heights of buildings will be $[3, 1, \underline{6}, 5, \underline{6}, 2]$.

It can be shown that it is impossible to make more than $2$ of the buildings cool, or to make $2$ buildings cool using fewer than $3$ additional floors.

In the fourth test case, Qpwoeirut can either make the second building cool, or he can make the third building cool. Either way, he will be building $3$ additional floors and maximizing the number of cool buildings. The final heights of buildings will be $[4, 2, \underline{4}, 3, 5, 3, 6, 1]$ or $[4, \underline{5}, 1, 3, 5, 3, 6, 1]$.

在第一个测试用例中，Qpwoeirut 的最优策略是在第二栋建筑上额外建造 $2$ 层，使其高于其两侧相邻的建筑，从而使其变得“酷”。最终各建筑的高度为 $[2, \underline{3}, 2]$。

在第二个测试用例中，“酷”建筑的数量已达到最大值，因此 Qpwoeirut 无需进行任何操作。

在第三个测试用例中，Qpwoeirut 的最优策略是让第三栋和第五栋建筑变得“酷”：在第三栋建筑上额外建造 $2$ 层，在第五栋建筑上额外建造 $1$ 层。最终各建筑的高度为 $[3, 1, \underline{6}, 5, \underline{6}, 2]$。

可以证明：无法使超过 $2$ 栋建筑变得“酷”，也无法仅用少于 $3$ 层的额外楼层就使 $2$ 栋建筑变得“酷”。

在第四个测试用例中，Qpwoeirut 可选择让第二栋建筑变得“酷”，也可选择让第三栋建筑变得“酷”。无论哪种方式，他都需要额外建造 $3$ 层，并且都能使“酷”建筑的数量达到最大值。最终各建筑的高度为 $[4, 2, \underline{4}, 3, 5, 3, 6, 1]$ 或 $[4, \underline{5}, 1, 3, 5, 3, 6, 1]$。