3194. 最大的矩形

在横轴上放了 $n$ 个相邻的矩形,每个矩形的宽度是 $1$,而第 $i$($1 ≤ i ≤ n$)个矩形的高度是 $h_i$。

这 $n$ 个矩形构成了一个直方图。

例如,下图中六个矩形的高度就分别是 $3, 1, 6, 5, 2, 3$。

p31.png

请找出能放在给定直方图里面积最大的矩形,它的边要与坐标轴平行。

对于上面给出的例子,最大矩形如下图所示的阴影部分,面积是 $10$。

p32.png

输入格式

第一行包含一个整数 $n$,即矩形的数量。

第二行包含 $n$ 个整数 $h_1, h_2, … , h_n$,相邻的数之间由空格分隔。$h_i$ 是第 $i$ 个矩形的高度。

输出格式

输出一行,包含一个整数,即给定直方图内的最大矩形的面积。

数据范围

$1 \le n \le 1000$,
$1 \le h_i \le 10000$

输入样例:

6
3 1 6 5 2 3

输出样例:

10