说明

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

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

输入格式

第一行一个整数 n

第二行 n 个整数 a[i]

输出格式

能画出的最大矩形的面积

样例

6
2 1 5 6 2 3

10

提示

数据解释：

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

数据范围：

• 1 <= n<=10⁵
• 0 <= a[i] <= 10⁴