题目描述

地表坑洼不平，每当暴雨来临地面上都会有一个个水洼。
又有一场暴雨即将来临，你决定改造地面来减少积水。
地面可抽象为一个长度为 $n$ 的正整数序列 $a$，其中 $a_i$ 表示当地的海拔高度。
下暴雨时将会汇聚在低洼处无法向两侧流走，比如一个序列 $a=[3,1,5,1,2,3]$。
在下雨后的积水如图所示（有 $5$ 格积水）：

由于人手不足，现在只来得及改变一个地方的海拔高度为任意正整数。

问改造后积水最少有几格。

输入格式

第一行一个整数 $T$。
接下来共 $T$ 组数据，每组数据占两行。
对于每组数据，第一行一个整数 $n$，表示序列长度。
第二行 $n$ 个整数，表示序列 $a$。

输出格式

对于每组数据输出一行一个整数，最小的积水格数。

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

2
0
1

提示

对于前 $5\%$ 的数据，$1\le n\le 5$。
对于前 $20\%$ 的数据，$1\le \sum n\le 550$，$1\le a_i\le 500$。
对于前 $35\%$ 的数据，$1\le \sum n\le 5050$，$1\le a_i\le 5000$。
对于前 $50\%$ 的数据，$1\le \sum n\le 5050$，$1\le a_i \le 10^9$。
对于 $100\%$ 的数据，$1\le n,\sum n\le 10^6$，$1\le a_i\le 10^9$。

保证 $1\le T\le 10^4$。