题目描述

kkk 做了一个人体感觉分析器。每一天，人都有一个感受值$A_i$，$A_i$越大，表示人感觉越舒适。在一段时间$left[i, j ight]$内，人的舒适程度定义为$left[i, j ight]$中最不舒服的那一天的感受值$ imes$$left[i, j ight]$中每一天感受值的和。现在给出 kkk 在连续$N$天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？

输入输出格式

输入格式

第一行为$N$，代表数据记录的天数。

第二行$N$个整数，代表每一天的感受值。

输出格式

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

输入输出样例

输入样例 #1

6
3 1 6 4 5 2

输出样例 #1

60

说明/提示

kkk 最开心的一段时间是第$3$天到第$5$天，开心值：$(6+4+5) imes4=60$。

对于$30\%$的数据，$1le Nle 100$。

对于$70\%$的数据，$1le Nle 2000$。

对于$100\%$的数据，$1le Nle 100000$，$1le exttt{感受值}le 1000000$。