题目描述

已知数轴上有 n 条直线，两条直线能围闭的矩形面积指的是以两条直线的间距为长，其中一条直线高度为宽所组成的矩形面积（如样例）。

给出每条直线的高度，求使用这些直线围闭一个矩形，能得到的最大面积是多少。

输入格式

第一行，一个正整数 n，表示有 n 条直线。

第二行，n 个正整数，按顺序给出每条直线的顺序。

数据范围

对于 40% 的数据， 1 <= n <= 1000 , 1 <= len[i] <= 10000 ;

对于 100% 的数据， 1 <= n <= 50000 , 1 <= len[i] <= 100000 。

输出格式

输出最大面积。

样例

9
1 8 6 2 5 4 8 3 7

49

样例解释

如下图所示，最大的面积是由第 2 、 9 条直线围闭的矩形，它的宽是 9 - 2 = 7，长是 7 ，因此面积为 49 。