题目描述

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

输入格式

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

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

输出格式

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

6
3 1 6 4 5 2

60

数据规模与约定

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

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

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

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