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?
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)$.
One line contains an integer represent the answer of the array.
5 1 2 3 4 5