← 返回题目列表

Codeforces · 1706/C

C. Qpwoeirut 和城市

中文机器翻译题面 查看原题

Qpwoeirut 开始从事建筑工作,并雄心勃勃地决定改造他的城市。

Qpwoeirut 的城市可以描述为一排 $$$n$$$ 建筑物,其中第 $$$i$$$ ($$$1 \le i \le n$$$) 层高为 $$$h_i$$$ 层。您可以假设此问题中每层楼的高度都是相等的。因此,建筑物 $$$i$$$ 比建筑物 $$$j$$$ 高当且仅当建筑物 $$$i$$$ 中的楼层数 $$$h_i$$$ 大于建筑物 $$$j$$$ 中的楼层数 $$$h_j$$$。

如果建筑物 $$$i$$$ 比建筑物 $$$i-1$$$ 和建筑物 $$$i+1$$$ 高(并且它们都存在),那么它很酷。请注意,第 $$$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 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - Qpwoeirut 需要建造的最小附加楼层数,以便最大限度地增加酷建筑的数量。

示例

输入 #1

6
3
2 1 2
5
1 2 1 4 3
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1
6
1 10 1 1 10 1
8
1 10 11 1 10 11 10 1

输出 #1

2
0
3
3
0
4

注意

在第一个测试用例中,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]$$$。