Trapping Rain Water

Given an elevation map where the width of each bar is 1, compute how much water can be trapped after raining. You are given an integer n followed by n non-negative integers representing the elevation map. The water trapped at each index i is given by \(\min(\text{left}_i, \text{right}_i) - \text{height}_i\), where \(\text{left}_i\) is the maximum height to the left of i (including i) and \(\text{right}_i\) is the maximum height to the right of i (including i). Your task is to compute the total amount of trapped water.

Note: If there are no bars (n = 0), then the trapped water is 0.

inputFormat

The first line contains a single integer n (0 ≤ n ≤ 10^5), indicating the number of bars. The second line contains n space-separated non-negative integers representing the elevation map. If n is 0, the second line may be omitted.

outputFormat

Output a single integer representing the total amount of water that can be trapped.## sample

0

0