2424 - 求最大面积

HISTOGRA-Largest Rectangle in a Histogram。如图所示，在一条水平线上有n个宽为1的矩形，问里面包含的矩形的最大面积是多少（图中的阴影部分的面积即所求答案）。

有多组测试数据，每组数据占一行。输入零时读入结束。

每行开头为一个数字n(1≤n≤10^5)，接下来在同一行给出n个数字h1，h2，…，hn(0≤hi≤10^9)，表示每个矩形的高度。

对于每组数据，输出最大子矩阵面积，一组数据输出一行。