Largest Rectangle in Histogram

Given a histogram represented by an array of non-negative integers, where each integer represents the height of a bar, find the area of the largest rectangle that can be formed within the histogram. The rectangle must be contiguous and can span multiple bars.

The area of a rectangle is computed as its height multiplied by its width. In mathematical terms, given a histogram with heights \(h[0\ldots n-1]\), the largest rectangle area is defined as:

\(\max_{0 \leq i \leq j < n}\left(\min\{h[i], h[i+1], \ldots, h[j]\} \times (j-i+1)\right)\)

Your task is to compute this maximum area.

inputFormat

The input is provided via standard input (stdin) and consists of two lines:

• The first line contains a single integer \(n\) which represents the number of bars in the histogram.
• The second line contains \(n\) space-separated non-negative integers that represent the heights of the histogram bars.

outputFormat

Output a single integer representing the area of the largest rectangle that can be formed in the histogram. The output should be written to standard output (stdout).

7
6 2 5 4 5 1 6

12