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