Maximum Rectangle Area in Histogram

You are given a histogram where the width of each bar is 1 and the heights of the bars are given in an array of integers. Your task is to find the largest area of a rectangle that can be formed using contiguous bars.

The area of a rectangle formed by a contiguous subset of bars is defined as:

[ \text{Area} = \text{height} \times \text{width} ]

where the height is the minimum bar height among the selected contiguous bars and the width is the number of bars selected.

Input Constraints: The array will contain at least one element and at most \(10^5\) elements. Each height is a non-negative integer.

Example:

Input:
1
5

Output:
5

In the above example, there is a single building with height 5, so the maximum rectangle area is 5.

inputFormat

The input is read from standard input (stdin) and contains two lines. The first line contains an integer \(n\), representing the number of buildings. The second line contains \(n\) space-separated integers, representing the heights of the buildings.

Example:

6
2 1 5 6 2 3

outputFormat

Output a single integer which is the maximum area of a rectangle that can be formed by choosing a contiguous subset of the given buildings. The output is printed on standard output (stdout).

Example:

10

## sample

1
5

5

</p>