题目描述

有 $N$ 个等间隔的位置，相邻位置之间的距离为 $1$。第 $i$ 个位置可以修建的池壁高度为 $A_i$。

选择两个不同的位置 $i,j$ 作为水池两端。水池宽度为 $|i-j|$，能够储水的高度由较矮的池壁决定，因此横截面积为 $|i-j|\times\min(A_i,A_j)$。

请计算水池横截面积的最大值。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出一个整数，表示最大横截面积。

样例

10
2 6 3 6 2 4 5 4 2 2

25

数据范围与提示

• 对于 $30\%$ 的数据，$2 \le N \le 20$，$1 \le A_i \le 50$
• 对于 $50\%$ 的数据，$2 \le N \le 500$，$1 \le A_i \le 1000$
• 对于 $70\%$ 的数据，$2 \le N \le 5000$，$1 \le A_i \le 1000$
• 对于 $100\%$ 的数据，$2 \le N \le 10^6$，$1 \le A_i \le 10^9$