Container With Most Water

You are given an array of non-negative integers where each integer represents the height of a vertical line on a coordinate plane. The width between each line is 1 unit. Find two lines, which together with the x-axis forms a container, such that the container contains the most water.

The area of water that the container can hold is computed by the formula:

where (h_i) and (h_j) are the heights of the two lines and (j-i) is the distance between them.

Your task is to find and output the maximum area of water the container can store.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (n) ((n \ge 2)), the number of vertical lines. The second line contains (n) space-separated non-negative integers representing the heights of the lines.

outputFormat

Output a single integer which is the maximum amount of water a container can store, printed to standard output (stdout).## sample

9
1 8 6 2 5 4 8 3 7

49