Maximum Product Subarray

Problem statement

A chain of experiments records signed multipliers. Choose a nonempty consecutive block whose product is greatest. A negative multiplier can turn a low product into a high one, and a zero can split the chain.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print the maximum product.

Constraints

1 <= n <= 100000; -10 <= value <= 10; every contiguous product fits a signed 64-bit integer.

Sample input

5
-2 3 -4 0 2

Sample output

24