Trapped Water Container

You are given an array of non-negative integers representing the heights of buildings. The goal is to determine the maximum amount of water that can be trapped between any two of these buildings.

Assume that the width between any two buildings is equal to the difference in their indices, and the height of the trapped water is limited by the shorter building. Formally, given an array heights, find the maximum area defined by

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

where \(0 \le i < j < n\). The answer is the maximum area that can be achieved by any two distinct buildings.

Example:

• Input: 9\n1 8 6 2 5 4 8 3 7, Output: 49
• Input: 5\n4 3 2 1 4, Output: 16
• Input: 3\n1 2 1, Output: 2

inputFormat

The first line of the input contains an integer n denoting the number of buildings. The second line contains n space-separated non-negative integers representing the heights of the buildings.

You should read from standard input (stdin).

outputFormat

Print a single integer which is the maximum area of water that can be trapped between any two buildings. The output should be written to standard output (stdout).

## sample

9
1 8 6 2 5 4 8 3 7

49

</p>