问题1763--接雨水

1763: 接雨水

时间限制: 1 Sec  内存限制: 128 MB
提交: 13  解决: 4
[提交] [状态] [讨论版] [命题人:]

题目描述

给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
比如高度为:0,1,0,2,1,0,1,3,2,1,2,1,可以接6个单位的雨水(下图蓝色部分表示雨水)



输入

两行
第一行为正整数n(n<=20000)
第二行为n个非负整数

输出

下雨之后能接多少雨水

样例输入 Copy

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

样例输出 Copy

6