Trapping Rain Water

You are given n non-negative integers representing an elevation map where the width of each bar is 1. The task is to compute how much water can be trapped after it rains.

The water trapped above each bar is determined by the formula:

\( \text{water}_i = \max\left(0, \min(\text{left\_max}_i, \text{right\_max}_i) - \text{height}_i \right) \)

where \( \text{left\_max}_i \) is the maximum height to the left of index i (including i) and \( \text{right\_max}_i \) is the maximum height to the right of index i (including i). The total trapped water is the sum of water trapped at each index.

It is guaranteed that all heights are non-negative integers.

inputFormat

Input is given from standard input (stdin). The first integer n denotes the number of buildings. The next n integers represent the heights of the buildings, separated by spaces.

Example: 6 0 1 0 2 1 0

outputFormat

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

Example: 1

## sample

6 0 1 0 2 1 0

1