Container With Most Water

You are given an array of non-negative integers where each integer represents the height of a building. Your task is to find two buildings such that the container formed between them can hold the maximum amount of water. The water contained is calculated by the formula:

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

where i and j (with i < j) are the indices of the chosen buildings. You need to output the maximum water that can be trapped by any two buildings.

inputFormat

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

Example:

9
1 8 6 2 5 4 8 3 7

outputFormat

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

Example:

49

## sample

9
1 8 6 2 5 4 8 3 7

49