#P9485. 「LAOI-1」积水

「LAOI-1」积水

题目描述

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

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

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

输入格式

第一行一个整数 TT
接下来共 TT 组数据,每组数据占两行。
对于每组数据,第一行一个整数 nn,表示序列长度。
第二行 nn 个整数,表示序列 aa

输出格式

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

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%5\% 的数据,1n51\le n\le 5
对于前 20%20\% 的数据,1n5501\le \sum n\le 5501ai5001\le a_i\le 500
对于前 35%35\% 的数据,1n50501\le \sum n\le 50501ai50001\le a_i\le 5000
对于前 50%50\% 的数据,1n50501\le \sum n\le 50501ai1091\le a_i \le 10^9
对于 100%100\% 的数据,1n,n1061\le n,\sum n\le 10^61ai1091\le a_i\le 10^9

保证 1T1041\le T\le 10^4