Largest Rectangle in Histogram

Given a histogram where the width of each bar is 1, your task is to compute the area of the largest rectangle that can be formed within the bounds of the histogram. The histogram is represented by a sequence of non-negative integers where each integer indicates the height of a bar. The rectangle must be formed by contiguous bars.

Note: The solution should correctly handle cases where the histogram bars are in increasing, decreasing, or random order.

inputFormat

The first line contains a single integer N denoting the number of bars in the histogram. The second line contains N space-separated non-negative integers, each representing the height of a histogram bar.

For example:

6
2 1 5 6 2 3

outputFormat

Output a single integer which is the maximum rectangular area that can be formed within the histogram.

For the sample input above, the correct output is:

10

## sample

6
2 1 5 6 2 3

10

</p>