CF1706C Qpwoeirut And The City

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 希望加建的楼层总数尽可能少。请你计算，为了让酷的建筑数量最大，Qpwoeirut 至少需要加建多少层楼。

第一行包含一个整数 $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 \times 10^5$。

对于每个测试用例，输出一个整数，表示为了让酷的建筑数量最大，Qpwoeirut 至少需要加建的楼层总数。

在第一个测试用例中，最优做法是让第二座建筑变成酷的，需要在其上加建 $2$ 层，使其比相邻的两座建筑都高。最终建筑高度为 $[2, \underline{3}, 2]$。  在第二个测试用例中，酷的建筑数量已经最大，无需加建楼层。 在第三个测试用例中，最优做法是让第三座和第五座建筑变成酷的，需要在第三座建筑上加建 $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]$。  由 ChatGPT 4.1 翻译