1523 - 小b接水
描述

小b将n个宽度相同的积木顺序摆在一起,如下图所示。

现在她告诉你每个积木的高度(可能为0)。

她想知道如果她从高处倒下一杯水,最多有多少单位的水能被积木接住?

假设每个积木的宽度都为1。

ak1j2qw4.png

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,最多可以接 6 个单位的水(蓝色

部分表示水)。


输入

第一行一个正整数n,其中0<n≤50000;  

第二行n个数表示从左到右每个积木的高度,以空格隔开,每个数不超过10000。


输出

一个数,表示最多可以接的水量

样例

输入

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

输出

6
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 33
通过次数 18