2424 - 求最大面积

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

16796209118390.png

输入

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

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

输出

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

样例

输入

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

输出

8
4000
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题