HISTOGRA - Largest Rectangle in a Histogram

### 题目描述 如图所示，在一条水平线上有 $n$ 个宽为 $1$ 的矩形，求包含于这些矩形的最大子矩形面积（图中的阴影部分的面积即所求答案）。 ### 输入格式： 有多组测试数据，每组数据占一行。输入零时读入结束。 每行开头为一个数字 $n(1\le n\le 10^5)$，接下来在同一行给出 $n$ 个数字 $h_1,h_2,\cdots, h_n (0\le hi\le 10^9)$，表示每个矩形的高度。 ### 输出格式： 对于每组数据，输出最大子矩阵面积，一组数据输出一行。

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:  Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

8
4000