#P2659. 美丽的序列

美丽的序列

题目背景

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。 提示 你可能需要一个读入优化。