题目描述

jyy 做了一个人体感觉分析器。每一天，人都有一个感受值 $\red{ A_i}$，$\red{ A_i}$ 越大，表示人感觉越舒适。

在一段时间[$\red i$, $\red j$]内，人的舒适程度定义为[$\red i$, $\red j$]中最不舒服的那一天的感受值 * [$\red{i,j}$]中每一天感受值的和。

现在给出 jyy 在连续 $\red N$ 天中的感受值，请问，在哪一段时间，jyy感觉最舒适？

输入格式

第一行为 $\red N$($\red{N <= 100000}$)，代表数据记录的天数。

第二行 $\red N$ 个整数，代表每一天的感受值(每个数不超过 $\red{1000000}$)。

输出格式

一行，表示在最舒适的一段时间中的感受值。

样例

输入样例

6
3 1 6 4 5 2

输出样例

60