Rainwater

Interview

Time limit1sMemory limit256 MB

Summary

Given stack heights across a 2D world, compute the total rainwater trapped between the blocks after heavy rain.

Level: Medium5 of 10
Topics: Array, Two pointers, Prefix sum, Implementation
Solved: No attempts yet

Problem

Blocks are stacked in a two dimensional world. When it rains, rainwater collects between the blocks.

It rains more than enough. How much rainwater collects in total?

Input

The first line contains the height $H$ and the width $W$ of the two dimensional world. ( $1 \le H, W \le 500$ )

The second line contains $W$ stack heights, given from the leftmost cell in order. Each height is an integer between $0$ and $H$ .

Blocks are piled up from the floor, so no empty space appears inside a stack. You may assume that the floor of the two dimensional world is always closed.

Output

One cell of the two dimensional world holds $1$ unit. Print the total amount of rainwater that collects.

If no rainwater collects at all, print $0$ .

Hint

Hint 1:

Hint 2:

Hint 3:

Examples3

Example 1
Input
```
4 4
3 0 1 4
```
Expected output
```
5
```
Example 2
Input
```
4 8
3 1 2 3 4 1 1 2
```
Expected output
```
5
```
Example 3
Input
```
3 5
0 0 0 2 0
```
Expected output
```
0
```