#P2422. 良好的感觉

良好的感觉

题目描述

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

输入格式

第一行为 NN,代表数据记录的天数。

第二行 NN 个整数,代表每一天的感受值。

输出格式

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

6
3 1 6 4 5 2
60

提示

kkk 最开心的一段时间是第 33 天到第 55 天,开心值:(6+4+5)×4=60(6+4+5)\times4=60

对于 30%30\% 的数据,1N1001\le N\le 100

对于 70%70\% 的数据,1N20001\le N\le 2000

对于 100%100\% 的数据,1N1000001\le N\le 1000001感受值10000001\le \texttt{感受值}\le 1000000