2059 - 最大矩形面积

给定一组非负整数组成的数组h,代表一组柱状图的高度,其中每个柱子的宽度都为1。 入参h为一个整型数组,代表每个柱子的高度,返回面积的值。

在这组柱状图中找到能组成的最大矩形的面积(如图所示)。

从左到右矩形的高度依次为2,1,4,5,1,3,3。能够找出的最大矩形面积为8

15807482656612.png

输入

输入包括两行,第一行包含一个整数n(1 ≤ n ≤ 20000)

第二行包括n个整数,表示h数组中的每个值,h_i(0 ≤ h_i ≤ 10000)

输出

输出一个整数,表示最大的矩阵面积。

样例

输入

6
2 1 5 6 2 3

输出

10

输入

7
1 4 4 4 4 1 1

输出

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