P2422 Good Feelings

{{}}

kkk built a human sensation analyzer. Each day, a person has a feeling value $A_i$; the larger $A_i$, the more comfortable the person feels. Over a time segment $\left[i, j\right]$, a person's comfort level is defined as the feeling value on the least comfortable day in $\left[i, j\right]$ $\times$ the sum of the feeling values of all days in $\left[i, j\right]$. Now, given kkk's feeling values over $N$ consecutive days, which time segment makes kkk feel the most comfortable?

The first line contains $N$, the number of days for which data was recorded. The second line contains $N$ integers, the feeling value of each day.

Output one line: the comfort value of the most comfortable time segment.

kkk's most comfortable time segment is from day $3$ to day $5$, comfort value: $(6+4+5)\times4=60$. Constraints: - For $30\%$ of the testdata, $1 \le N \le 100$. - For $70\%$ of the testdata, $1 \le N \le 2000$. - For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le$ feeling value $\le 10^6$.}} Translated by ChatGPT 5