题目背景

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

题目描述

为了研究这个序列的美丽程度，GD 定义了一个序列的“美丽度”和“美丽系数”：

• 对于这个序列的任意一个区间 $[l,r]$，这个区间的“美丽度”就是这个区间的长度与这个区间的最小值的乘积。
• 而整个序列的“美丽系数”就是它的所有区间的“美丽度”的最大值。

现在 GD 想要你帮忙计算这个序列的“美丽系数”。

输入格式

第一行一个整数 $n$，代表序列中的元素个数。

第二行 $n$ 个整数 $a_i \sim a_n$，描述这个序列。

输出格式

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

3 
1 2 3

4

提示

样例解释

选取区间 $[2,3]$，可以获得最大的“美丽系数”，为 $2 \times 2=4$。

数据范围

• 对于 $20\%$ 的数据，$n \le 2 \times 10^3$；
• 对于 $60\%$ 的数据，$n \le 2 \times 10^5$；
• 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^6$，$0 \le a_i \le 2 \times 10^6$。

提示

你可能需要一个读入优化。