题目描述

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

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

输入格式

第一行一个正整数n(1≤n≤10^5)；

第二行n个不大于10000的正整数。

输出格式

一个整数代表最大的矩形面积。

输入/输出样例

6
2 1 5 6 2 3

10

8
2 3 4 1 5 6 4 2

12

说明/提示

时间1000ms，内存256MiB