Largest Rectangle in Histogram

Given an array representing the heights of buildings, your task is to find the area of the largest rectangle that can be formed by any contiguous subsequence of these buildings. The area of a rectangle covering buildings from index (i) to (j) is defined as (A = (j - i + 1) \times \min_{i \leq k \leq j} {h_k}), where (h_k) denotes the height of the (k)-th building.

Implement a program that reads the input from standard input and writes the result to standard output.

inputFormat

The input consists of two lines. The first line contains an integer (n) which represents the number of buildings. The second line contains (n) space-separated integers, each representing the height of a building. If (n = 0), there will be no second line.

outputFormat

Output a single integer representing the maximum rectangular area that can be formed in the given histogram.## sample

6
2 1 5 6 2 3

10