Trapping Rain Water

Given the non-negative heights of n adjacent bars, each of width 1, compute the total units of water these bars can trap after rain. There are no extra walls at the ends, so water can flow out. The original snapshot's text is truncated, but the starter explicitly references LC42; this site completed the width and water-trapping definitions from that official statement, and the two original examples and full constraints agree with the official version.

输入格式

Input n, followed by n heights, separated by whitespace. Full original range 1≤n≤20000, 0≤height[i]≤100000; empty arrays are not accepted. The standard input is this site's adaptation of the array parameter.

输出格式

Output the total units of rain water trapped, as an exact integer with no modulo.

样例 1

输入：

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

输出：

6

样例 2

输入：

6
4 2 0 3 2 5

输出：

9

样例 3

输入：

3
2 0 2

输出：

2

样例说明

The two original examples keep 6 and 9; the third example [2,0,2]→2 is added by this site. The source text was truncated rather than defining different rules.