Maximal Rectangle Area in a Histogram

Given a histogram represented by a sequence of non-negative integer heights, your task is to compute the area of the largest rectangle that can be formed within the bounds of the histogram. The rectangle must be formed by contiguous bars. Formally, for a histogram given as an array (h[0 \ldots n-1]), the area of the rectangle spanning from index (i) to (j) is given by (A = (j-i+1) \times \min{h[i], h[i+1], \dots, h[j]}). Your goal is to find the maximum such area over all possible contiguous segments of the histogram.

inputFormat

The input is given from standard input (stdin) and consists of two lines. The first line contains a single integer (n) ((1 \leq n \leq 10^5)) representing the number of bars in the histogram. The second line contains (n) space-separated integers representing the heights of the bars.

outputFormat

Output a single integer to standard output (stdout) which is the largest rectangular area that can be formed within the given histogram.## sample

7
2 1 4 5 1 3 3

8