Largest Rectangle in Histogram

Given an array of non-negative integers representing the height of each bar in a histogram (with a unit width for every bar), your task is to find the area of the largest rectangle that can be formed within the bounds of the histogram.

The rectangle is formed by selecting consecutive bars, and its area is computed as ( \text{area} = \text{width} \times \min(\text{heights}) ).

inputFormat

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

outputFormat

Output a single integer representing the area of the largest rectangle that can be formed in the histogram.## sample

6
2 1 5 6 2 3

10