Largest Rectangle in Histogram

You are given a histogram represented by n bars, where the width of each bar is 1 and its height is given by an integer. Your task is to find the area of the largest rectangle that can be formed within the histogram. The rectangle must be formed by consecutive bars.

More formally, if the histogram is represented as an array heights of size n, you need to find the maximum value of:

[ \text{Area} = h \times w, ]

where h is the minimum height among a contiguous subarray of bars and w is the number of bars in that subarray. For instance, if heights = [2,1,5,6,2,3], the largest rectangle has an area of 10.

Note: If the histogram is empty (n = 0), the maximum rectangle area is 0.

inputFormat

The input is provided via standard input (stdin) and consists of two lines. The first line contains a single integer n (where n ≥ 0), which represents the number of bars in the histogram. The second line contains n space-separated non-negative integers representing the heights of each bar. If n = 0, the second line will be empty.

outputFormat

Output a single integer via standard output (stdout), representing the maximum rectangular area that can be obtained in the histogram.

## sample

6
2 1 5 6 2 3

10

</p>