Container With Most Water

You are given an array of non-negative integers where each element represents the height of a building. The task is to find two buildings that, together with the x-axis, form a container such that the container holds the maximum amount of water. The water contained is determined by the distance between the two buildings and the height of the shorter one.

The area (or amount of water contained) is given by the formula:

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

If there are fewer than 2 buildings, the answer is 0.

inputFormat

The first line contains a single integer n (0 ≤ n ≤ 10⁵), representing the number of buildings. The second line contains n space-separated non-negative integers representing the heights of the buildings.

outputFormat

Output a single integer which is the maximum amount of water that can be trapped between two buildings.

9
1 8 6 2 5 4 8 3 7

49