1966: 阳台接雨

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:160 解决:40

题目描述

家里阳台有一排水平摆放的花架,均匀固定了 n 块垂直挡板(挡板底部与花架贴合,无空隙)。设第 i 块挡板的高度为 aᵢ(单位:米,i=1,2,…,n),相邻挡板无空隙。

暴雨后雨水均匀落在花架上且无渗漏,积水高度遵循 “不超过两侧挡板的最低值、不溢出当前挡板” 的规则(即某位置积水高度 = 该位置左右两侧最高挡板中的较低值 - 当前挡板高度,若结果为负则无积水)。每 1 立方米雨水可浇灌 1 盆花,这排花架最多能储存多少立方米雨水?

输入

第一行一个整数n,表示n块挡板。

接下来是挡板高度数组H=[a1,a2,...,an]

输出

一个整数,表示这排花架最多能储存的立方米雨水。

样例输入 复制

12
0 1 0 2 1 0 1 3 2 1 2 1

样例输出 复制

6

提示


1 <= n <= 2 * 10^4
0 <= a[i] <= 10^5



来源/分类