题目描述

"水晶"是一个热爱读书的人，尤其喜欢地理相关的书籍，他的书架上整齐地摆放着各种类型的地理书。每当有空闲时间，水晶总会手捧一本地理书，沉浸在地理的世界中，从中汲取知识和灵感，这是他最好的朋友。

有一天，水晶觉得书架上的书太乱了，想要整理一下，但是又不想改变书的顺序。

为了让书看起来更整齐，水晶决定去买若干个木板把若干本书垫起来（每本书的厚度都相同，若木板的长度为 $k$ ，则这个木板可以使连续 $k$ 本书的高度加 $1$ ）。

水晶想知道，最少用多少个木板才能使书的最终高度从左到右先递增再递减（非严格）？

如图，这是一种合理的划分方法，从左到右红色部分递增而蓝色部分递减。

$\textbf{注意1：任何木板都不能有悬空的部分。}$

$\textbf{注意2：存在任意一个分界点使其满足条件即可。}$

$\textbf{注意3：若只有一本书则视为已经合法。}$

输入格式

本题有 $\textbf{多组数据}$ ，第一行输入一个 $t(1\le t\le 1000)$ ，表示测试用例的数量。

对于每个测试用例：

第一行输入一个 $n(1\le n\le 10^5)$ ，代表书的数量。

第二行输入 $a_1, a_2, a_3, ..., a_n(1\le a_i\le 10^9)$ ，其中 $a_i$ 表示从左往右第 $i$ 本书的初始高度。

保证所有测试用例的 $n$ 之和不超过 $2\times 10^5$ 。

对于每个测试用例，输出一个整数，表示使书的高度从左到右先递增再递减最少需要的木板数量。

3
3
7 6 8
2
1 9
6
1 2 3 2 2 1

1
0
0

第一组样例，只需使用长度为 $1$ 的木板把中间的书垫起来即可：左 $[7, 7]$ 和右 $[8]$ 满足条件。

第二组样例，书的高度已经满足条件，无需再垫木板：左 $[1]$ 和右 $[9]$ 满足条件。

第三组样例，书的高度已经满足条件，无需再垫木板：左 $[1, 2, 3]$ 和右 $[2, 2, 1]$ 满足条件。