Maximum Water Trapped Between Two Buildings

You are given n buildings in a row with positive integer heights. Your task is to choose two different buildings and compute the maximum amount of water that can be trapped between them. The amount of water trapped between two buildings is determined by the formula:

\( \text{water} = \min(\text{height}_i, \text{height}_j) \times (j - i) \)

where i and j are the indices of the two buildings (with 0-based indexing) and \(j > i\). The objective is to maximize this value.

Note: The input is provided as two lines. The first line contains an integer \(n\) representing the number of buildings. The second line contains \(n\) space-separated integers that denote the heights of the buildings. You should output the maximum water that can be trapped between any two buildings.

inputFormat

The first line contains an integer \(n\) (\(n \ge 2\)), representing the number of buildings.

The second line contains \(n\) space-separated integers \(h_1, h_2, \dots, h_n\) representing the heights of the buildings.

outputFormat

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

9
1 8 6 2 5 4 8 3 7

49