Largest Rectangle in Histogram

Given a histogram represented by a sequence of non-negative integers, where each integer corresponds to the height of a bar, your task is to compute the area of the largest rectangle that can be formed within the bounds of the histogram. The rectangle must be fully contained within the histogram and its area is defined by ( \text{area} = \text{height} \times \text{width} ).

Note: The rectangle’s height is determined by the shortest bar within the selected contiguous segment.

inputFormat

The input is read from standard input (stdin).

The first line contains an integer ( n ) representing the number of bars in the histogram. The second line contains ( n ) space-separated integers representing the heights of the histogram bars.

outputFormat

Output a single integer to standard output (stdout) which is the maximum rectangular area that can be obtained within the histogram.## sample

6
2 1 5 6 2 3

10