Container With Most Water

You are given an array of n non-negative integers where each integer represents the height of a vertical line drawn at that index. The distance between adjacent lines is 1.

The task is to choose two different lines, say at indices i and j with i < j, and compute the area of water the container can hold. The area is calculated by the formula:

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

Your goal is to find the maximum area achievable by any such pair of lines.

inputFormat

The first line of input contains an integer n, which represents the number of vertical lines.

The second line contains n space-separated non-negative integers, where each integer represents the height of a line.

outputFormat

Output a single integer representing the maximum water area that can be contained.

9
1 8 6 2 5 4 8 3 7

49