最大矩形

最大矩形

测试数据来自 system/1580

描述

在x轴上水平放置着N个条形图,这N个条形图就组成了一个柱状图,每个条形图都是一个矩形,每个矩形都有相同的宽度,但是它们的高度并不相同。

比如,图1包含的矩形的高分别为2,1,4,5,1,3,3单位长度,矩形的宽为1单位长度。

你的任务就是计算柱状图中以x轴为底边的最大矩形的面积。图2阴影部分就是上述例子的最大矩形面积。

格式

输入格式

一组数据包含若干行,每行是一个整数N(1≤N≤100,000),表示柱状图包含N个矩形。紧接着N个整数h1,...,hn(0≤ hi ≤20,000, 1≤ i≤ N),表示柱状图中按从左到右顺序给出的矩形的高度。矩形的宽度为1。

输出格式

输出若干行,每行一个整数S,表示以x轴为底边的最大矩形的面积。

样例1

样例输入1

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

样例输出1

4000
8
0

限制

一个测试点1s

提示

最后输出0表示结束

信息

ID
1662
难度
(无)
分类
数据结构 | 单调队列 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者