Largest Rectangle in a Histogram

You are given a histogram represented by an array of non-negative integers where each integer denotes the height of a building and the width of each building is 1. Your task is to compute the area of the largest rectangle that can be formed in the histogram.

The problem can be mathematically described as follows: Given an array (H = [h_1, h_2, \dots, h_n]), find the maximum area (A) where (A = \max_{1 \leq i \leq j \leq n} { (j - i + 1) \times \min{h_i, h_{i+1}, \dots, h_j} }).

The input is taken from the standard input (stdin) and the output should be printed to the standard output (stdout).

inputFormat

The first line contains an integer (n) representing the number of buildings in the histogram. The second line contains (n) space-separated non-negative integers representing the heights of the buildings. If (n = 0), then there are no further inputs.

outputFormat

Print a single integer, the maximum area of the rectangle that can be formed in the given histogram.## sample

7
2 1 5 6 2 3 4

10