Description

在数学课上，老师教小明柱形图。小明感到很神奇。为了方便观察，小明把柱形图的横坐标和纵坐标去掉，把相邻的两根柱都紧密靠在一起，每一根柱的宽为1。他想在简化的柱形图里找一个面积最大的长方形。

如图：

上图为简化后的柱形图，最大面积为3*4=12，最大的长方形面积方案可能不唯一，如上图红色部分是其中一种方案。

Input Format

第一行为正整数n，表示柱的数量。

第二行有n个正整数，表示从左到右柱子的高度。

Output Format

    只有一行为最大的长方形面积。

5
2 5 4 5 3 

12

Hint

30%的数据n<=100

60%的数据n<=1000

100%的数据n<=100000 每一根柱的高度不超过10000。

Source