ヒストグラムの中の最大長方形

ヒストグラムは縦軸に度数、横軸に階級をとった統計グラフです。ヒストグラムは、幅が等しく高さが度数を表す長方形を、下端を揃えて横に並べて描かれます。

幅が１、高さがそれぞれ $h_1, h_2, ... , h_N$ の $N$ 個の長方形で表されたヒストグラムに含まれる、長方形の面積の最大値を求めてください。

Constraints

• $1 \leq N \leq 10^5$
• $0 \leq h_i \leq 10^9$

Input

入力は以下の形式で与えられる。

$N$
$h_1$ $h_2$ ... $h_N$

Output

面積の最大値を１行に出力してください。

Sample Input 1

8
2 1 3 5 3 4 2 1

Sample Output 1

12

Sample Input 2

3
2 0 1

Sample Output 2

2

---