城市改造

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

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 至少需要加建的楼层总数。

样例输入 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

数据范围

对于所有数据，$1\le t\le10^4$，$3\le n\le10^5$，$1\le h_i\le10^9$；所有测试用例中 $n$ 的总和不超过 $2\times10^5$。