1652: 暑期练习题2

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：2 Solved：1

Description

少年宫玩中学小组的小朋友们，用各种长度的乐高柱子拼搭了城市高楼的积木图形，现在给你 n 个正整数，用来表示积木块柱子的高度。每个柱子彼此相邻，且宽度为 1 。请你在该乐高积木块图形中，找出矩形的最大面积。 
示例 1:
输入：n=7 height = [2 1 2 3 4 2 1] 输出：8 。   解释：最大的矩形为图中紫色区域，面积为 8。

如下图示: (紫色的矩形为最大)


Input

 输入第一行输入一个正整数n（1≤n≤1000000），表示有n列柱状积木块。第二行输入n个正整数（1≤正整数≤10000），表示每列柱状积木块高度，两个正整数之间用一个空格隔开。


Output

 输出一个正整数，表示能够找到的出矩形的最大面积。

Sample Input Copy 

7
2 1 2 3 4 2 1

Sample Output Copy 

8

HINT

提示:

给定的N（1≤N≤10^7），每一列柱状积木块高度（1≤高度≤10^4）