柱状图中最大的矩形

题目描述

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

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

输入

第一行数字n

第二行n个数字，a_i表示柱状图中各个柱子的高度

输出

能够勾勒出来的矩形的最大面积。

样例

提示

样例1

样例2

n \leq 10^5 , a_i \leq 10^4

来源

leetcode