Container With Most Water

You are given n vertical lines, where the i-th line has a non-negative integer height h_i. The lines are drawn on a coordinate plane at positions i from 0 to n-1.

Find two lines that together with the x-axis form a container, such that the container contains the most water. Note that the area of water that can be contained is determined by the distance between the two lines multiplied by the minimum of their two heights. In other words, if you choose lines at positions i and j (with i < j), the area is computed as:

\(Area = (j-i) \times \min(h_i, h_j)\)

Your task is to compute this maximum area.

inputFormat

The input is given via standard input (stdin) and consists of two lines.

• The first line contains an integer n (2 ≤ n ≤ 10⁵), representing 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 representing the maximum area of water that can be contained.

9
1 8 6 2 5 4 8 3 7

49