Rainwater

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

Medium5ArrayTwo pointersPrefix sumImplementationInterviewNo attempts yetTime limit1sMemory limit256 MB

Description

Examples3

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: