#P9485. 「LAOI-1」积水
「LAOI-1」积水
题目描述
地表坑洼不平,每当暴雨来临地面上都会有一个个水洼。
又有一场暴雨即将来临,你决定改造地面来减少积水。
地面可抽象为一个长度为 的正整数序列 ,其中 表示当地的海拔高度。
下暴雨时将会汇聚在低洼处无法向两侧流走,比如一个序列 。
在下雨后的积水如图所示(有 格积水):
由于人手不足,现在只来得及改变一个地方的海拔高度为任意正整数。
问改造后积水最少有几格。
输入格式
第一行一个整数 。
接下来共 组数据,每组数据占两行。
对于每组数据,第一行一个整数 ,表示序列长度。
第二行 个整数,表示序列 。
输出格式
对于每组数据输出一行一个整数,最小的积水格数。
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
提示
对于前 的数据,。
对于前 的数据,,。
对于前 的数据,,。
对于前 的数据,,。
对于 的数据,,。
保证 。