题目描述

在数轴的整数位置1至 $n$ 各有一条竖直线，高度为 $h_i$。选择位置 $i<j$ 的两条线，以它们的间距为宽、较短线的高度为高，形成面积 $(j-i)\min(h_i,h_j)$ 的矩形。求最大面积；不足两条线时输出0。

输入格式

第一行 $n$；第二行 $n$ 个高度。

输出格式

输出最大面积。

样例

9
1 8 6 2 5 4 8 3 7

49

数据范围

40%的数据：$n\le1000$，$h_i\le1000$。

100%的数据：$1\le n\le50000$，$1\le h_i\le10000$。