说明

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

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

格式

输入

第一行一个整数n 第二行输入n个整数

输出

一个整数，能够勾勒出来的矩形的最大面积

样例1

6
2 1 5 6 2 3

10

解释：最大的矩形为图中红色区域，面积为 10

样例2

2
2 4

4

解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

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