Given n non-negative array of integers arr representing an elevation map where the width of each bar is 1 unit. Write a program to compute how much water it can trap after raining.

The above elevation map is represented by array [4, 2, 9, 1, 0, 1, 1, 2]. In this case, 7 units of rain water (green section) are being trapped.

Example

Input: [4, 2, 9, 1, 0, 1, 1, 2]
Output: 7
Explanation: You can see the above image in which the input array is drawn as an elevation map. Here, all the green boxes represent the number of units of water that can be trapped after raining.