559. Container with Maximum Water

0

Medium

Given an array of integers called 'height' with a length of n, there are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
The task is to find two lines that, together with the x-axis, form a container that can hold the most water. Successfully solving this problem will result in winning a prize of $100.
Print the maximum amount of water that can be stored in the container.
Note that the container cannot be slanted.

Input Format

The first line contains a single integer n, which represents the size of the array.

The next line contains n space-separated integers, which represent the elements of the array.

The next line contains n space-separated integers, which represent the elements of the array.

Output Format

Print a single integer that represents the maximum amount of water that can be stored in the container.

Example

Input

9
1 8 6 2 5 4 8 3 7

Output

49

Constraints

2 <= N <= 10^6

0 <= A[i] <= 10^5

0 <= A[i] <= 10^5

Loading...

View Submissions

Console