Largest Rectangle in Histogram

Given a histogram consisting of non-negative integers, determine the largest rectangular area that can be formed within the histogram. A rectangle is defined by consecutive bars and its area is computed as the product of the width (number of consecutive bars) and the minimum height among those bars. Formally, if the rectangle spans from index i to j, then its area is given by:

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

Input is read from standard input and output is written to standard output. Your task is to compute the maximum area possible.

inputFormat

The input consists of two lines:

1. The first line contains a single integer n representing the number of bars in the histogram.
2. The second line contains n space-separated non-negative integers representing the heights of the histogram bars. If n is 0, the second line may be omitted.

outputFormat

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

6
2 1 5 6 2 3

10