接雨水

题目描述

给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

例如，当给定数字序列为0,1,0,2,1,0,1,3,2,1,2,1时，柱子高度图如下所示，最多可以接6个单位的雨水。

输入描述

第一行包含整数n。

第二行包含n个非负整数。

数据范围：

1≤n≤10^5,

序列中元素均不大于1000。

输出描述

输出一个整数，表示最大接水量。