暂无测试数据。

蒜头君就要放暑假了，他通过计算机预测出他暑假 $n$ 中每天的兴奋值 $a_i$ 。从第 $x$ 天开始到第 $y$ 天这段时间的心情值定义为 $\min\lbrace a_k,k\in[x,y] \rbrace \times \sum\limits _{k=x}^y a_k$。现在找出在暑假中哪段时间内蒜头君的心情值的最大，求出这个最大的心情值。

输入格式

第一行一个整数 $n\ (1\le n \le 10^5)$，表示暑假的天数。

第二行 $N$ 个整数，每个整数 $a_i\ (1\le a_i \le 10^6)$ 代表第 $i$ 天的的兴奋值。

输出格式

一个整数，表示心情值的最大值。

样例解释

第三天到第五天的心情值最大，为 $4\times (6+4+5)=60$。

6
3 1 6 4 5 2

60