Trapped Rain Water

You are given an array of non-negative integers (h_1, h_2, \dots, h_n) where each (h_i) represents the height of a pillar. When it rains, water is trapped between the pillars. The water above a pillar at index (i) can be computed as (\min(L_i, R_i) - h_i), where (L_i) is the maximum height to the left of index (i) and (R_i) is the maximum height to the right of index (i). Your goal is to calculate the total amount of water that can be trapped between the pillars.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) representing the number of pillars. The second line contains (n) space-separated integers representing the heights of the pillars.

outputFormat

Output a single integer to standard output (stdout), which is the total amount of trapped water.## sample

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

6