美丽的序列

GD是一个热衷于寻求美好事物的人，一天他拿到了一个美丽的序列。

为了研究这个序列的美丽程度，GD定义了一个序列的“美丽度”和“美丽系数”：对于这个序列的任意一个区间[l，r]，这个区间的“美丽度”就是这个区间的长度与这个区间的最小值的乘积，而整个序列的“美丽系数”就是它的所有区间的“美丽度”的最大值。现在GD想要你帮忙计算这个序列的“美丽系数”。

第一行一个整数n，代表序列中的元素个数。 第二行n个整数a1、a2„an，描述这个序列。

一行一个整数，代表这个序列的“美丽系数”。

3 
1 2 3

4

样例解释 选取区间［2，3］，可以获得最大“美丽系数”为2\*2=4。 数据范围 对于20%的数据，n<=2000； 对于60%的数据，n<=200000； 对于100%的数据，1<=n<=2000000，0<=ai<=2000000。 提示 你可能需要一个读入优化。