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]$$$。