该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

给定有 n 个正整数构成的序列 A，定义一段连续的子序列 A[p .. q]的价值为： Min(a[i]) * sigma(a[i]) （p <= i <= q） 你需要找出其中价值最大的一段子序列。

Format

Input

第一行一个正整数 N 表示序列的长度（1 <= n <= 100000）。 然后 n 个[1 .. 106]的正整数给出 A。

Output

仅一行一个正整数 V，表示最大的价值。

Samples

6 
3 1 6 4 5 2

60

Limitation

30%的数据,N<=100 100%的数据,N<=100000