×

计蒜客

  1. 题库
  2. Max answer
  3. 问答
  • 11.8%
  • 262144K

Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.

Now she is planning to find the max value of the intervals in her array. Can you help her?

Input

First line contains an integer $n(1 \le n \le 5 \times 10 ^5$).

Second line contains $n$ integers represent the array $a (-10^5 \le a_i \le 10^5)$.

Output

One line contains an integer represent the answer of the array.

样例输入

5
1 2 3 4 5

样例输出

36

想挑战这道题吗

  • main.c