Largest Rectangle in Histogram

Given a histogram where the width of each bar is 1, find the area of the largest rectangle that can be formed within the bounds of the histogram.

The histogram is represented by an array of positive integers. For each bar, its height is given by the corresponding integer, and the width is assumed to be 1. The largest rectangle can span multiple consecutive bars. Formally, if you choose bars from index i to index j, the area of the rectangle is given by:

\( \text{area} = \min_{i \leq k \leq j} (\text{heights}[k]) \times (j-i+1) \)

Your task is to compute the maximum such area over all possible contiguous segments.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

The first line contains a single integer n, the number of bars in the histogram. The second line contains n space-separated positive integers representing the heights of the histogram's bars.

outputFormat

Print to standard output (stdout) a single integer: the area of the largest rectangle that can be formed in the histogram.## sample

6
2 1 5 6 2 3

10