接雨水

题目描述

给定 n 个非负整数 height[i]，表示宽度为 1 的柱子的高度。

请计算按此排列的柱子在下雨之后最多可以接多少单位的雨水。

输入格式

第一行输入一个整数 n。

第二行输入 n 个非负整数，表示数组 height。

输出格式

输出一个整数，表示最多可以接到的雨水总量。

数据范围

1 <= n <= 2 * 10^4

0 <= height[i] <= 10^5

样例 1

输入

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

输出

6

样例 2

输入

6
4 2 0 3 2 5

输出

9