Maximum Comfort Interval

kkk has built a human sensation analyzer. Each day, a person has a sensation value \(A_i\), where a larger \(A_i\) indicates a higher level of comfort. For any contiguous interval \([i, j]\), the comfort level is defined as the product of the minimum sensation value in the interval and the sum of all sensation values in the interval. In other words, for an interval \([i,j]\), its comfort level is:

\( f(i,j) = \min\{A_i, A_{i+1},\dots,A_j\} \times \sum_{k=i}^{j} A_k \)

Given the sensation values over \(N\) consecutive days, determine the interval where kkk feels the most comfortable, i.e. the interval with the maximum comfort level.

inputFormat

The input begins with a positive integer \(N\) (the number of days). The next line contains \(N\) space-separated integers \(A_1, A_2, \dots, A_N\), representing the sensation values for each day.

Constraints: \(1 \leq N \leq 10^5\); \(1 \leq A_i \leq 10^9\).

outputFormat

Output a single integer, the maximum comfort level that can be achieved by selecting an appropriate contiguous interval.

sample

5
1 2 3 2 1

14