629. Trapping Rain Water
0
Hard
Tushar, a rain harvester, possesses a collection of N bars. Each bar has a specific height and a width of 1 unit. Determine the amount of water that can be trapped by these bars after the next rainfall.
Input Format
The first line of input consists of an integer N, representing the number of bars.
The second line of input consists of N integers, indicating the height of each bar respectively.
The second line of input consists of N integers, indicating the height of each bar respectively.
Output Format
Print the amount of water contained by this set of bars after the next rainfall.
Example
Input
12
0 1 0 2 1 0 1 3 2 1 2 1
Output
6
Constraints
1<=N<=10^5
0<=height<=10^5
0<=height<=10^5
Loading...
View Submissions
Console