Container With Most Water

Given an array of n non-negative integers, where each integer represents the height of a vertical line on the x-axis, your task is to find two lines that together with the x-axis form a container, such that the container contains the maximum amount of water.

The amount of water a container can store is determined by the formula: \(\text{Area} = \min(\text{height}_i, \text{height}_j) \times (j - i)\), where \(i\) and \(j\) are the positions of the two lines. Your program should compute and output the maximum area possible.

inputFormat

The first line of input contains an integer n (\(1 \leq n \leq 10^5\)), representing the number of vertical lines. The second line contains n space-separated non-negative integers, where the i-th integer represents the height of the i-th line.

outputFormat

Output a single integer which is the maximum area of water that can be contained.

9
1 8 6 2 5 4 8 3 7

49