该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一条街道上从左到右依次有 $n$ 栋楼房，第 $i$ 栋楼房有 $h_i$ 层。如果第 $i$ 栋楼房比它左右相邻的两栋都高， 就称第 $i$ 栋楼房是酷的（第 $1$ 栋与第 $n$ 栋楼房不可能酷）。

33DAI 想给楼房加盖楼层，让尽可能多的楼房变酷。加盖只能增加层数，不能拆掉已有的楼层。 加盖楼层很花钱，所以他希望花最少的钱达到这个目的：先在可以让尽可能多的楼房变酷的前提下， 再让加盖的总层数尽可能少。

输入格式

从文件 city.in 读入数据。

输入的第一行包含一个整数 $t$，表示测试数据组数。

接下来依次给出 $t$ 组数据，每组数据的格式为：

第一行包含一个整数 $n$，表示楼房数量。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$，其中 $h_i$ 表示第 $i$ 栋楼房的层数。

输出格式

输出到文件 city.out。

对于每组数据，输出一行一个整数，表示让酷的楼房尽可能多时最少需要加盖的层数。

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

2
0
3
3
0
4

样例 1 解释

下面是一种最终的状态方案

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

样例 2

见 city2.in 与 city2.ans。

样例 3

见 city3.in 与 city3.ans。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 10^4$；
• $3 \le n \le 10^5$；
• $1 \le h_i \le 10^9$；
• 单个测试文件中所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。