Background

{{}}

Problem Description

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?

Input Format

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 Format

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

6
3 1 6 4 5 2

60

Hint

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