5958: 【系列题】单调栈(五)柱状图中最大的矩形

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:7 Solved:4

Description

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

Input

第一行一个整数 n

第二行 n 个整数 a[i]

Output

能画出的最大矩形的面积

Sample Input Copy

6
2 1 5 6 2 3

Sample Output Copy

10

HINT

数据解释:

解释:如果输入为[2,4],则两种画法面积都为4。


数据范围:

  • 1 <= n<=105
  • 0 <= a[i] <= 104