Container With Most Water

Problem Statement

You are given n vertical lines on a 2D plane. The i-th line has a non-negative integer height height[i] and is drawn at coordinate i (i.e. its two endpoints are (i, 0) and (i, height[i])). Find two lines such that together with the x-axis they form a container, which can hold the maximum amount of water.

The amount of water contained is determined by the formula

$\text{Area} = \min(height[i],\; height[j]) \times (j - i)$

where i and j are the indices of the two selected lines with i < j. Your task is to compute the maximum area of water that can be contained.

Note: The container cannot be tilted.

inputFormat

The first line of input contains a single integer (n), denoting 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 that can be contained by any two lines.## sample

9
1 8 6 2 5 4 8 3 7

49