Largest Rectangle in a Histogram

Given an array of non-negative integers representing the heights of histogram bars, your task is to compute the area of the largest rectangle that can be fit entirely under the histogram.

For a bar of height (h) that spans a contiguous block of bars of width (w), the area is given by the formula:

(\text{Area} = h \times w).

The rectangle must be formed by one or more consecutive bars. If the input array is empty, the maximum area is 0.

inputFormat

The input is given via stdin and consists of two lines.

The first line contains a single integer (n) representing the number of histogram bars.

The second line contains (n) space-separated non-negative integers representing the heights of the bars.

outputFormat

Output a single integer to stdout: the maximum area of a rectangle that can be formed in the histogram.## sample

6
2 1 5 6 2 3

10