Curious George is feeling curious. While normally he has a banana, today he is holding onto the array \(a\) of length \(N\) (\(2 \le N \le 10^5\)).

Are you curious about what he's curious about?

He wonders, if he chooses any two non-overlapping and non-empty subarrays in \(a\), what is the maximum possible product of the sums of the subarrays?

Note:
A subarray is defined as a contiguous part of an array.
It's non-empty if it contains nonzero number of elements.
Two subarrays are non-overlapping if they don't intersect.

Input Specification

The first line contains the integer \(N\).
The next line contains \(N\) integers (\(-10^3 \le a_i \le 10^3\)).

For \(18/28\) of the subtasks, \(N \le 100\).
For \(28/28\) of the subtasks, \(N \le 10^5\).

Output Specification

What is the maximum possible product?
The answer is guaranteed to fit in a \(64\)-bit integer.

Sample Input

6
-1 4 2 -2 8 -2

Sample Output

48

To get the maximal product, Curious George should choose the two subarrays \([4, 2]\) (index \(2\) to \(3\)) and \([8]\) (index \(5\) to \(5\)).
Note that they are non-empty and non-overlapping.
(\(4+2\)) \(\times\) (\(8\)) = \(48\)