A foundry applies n consecutive integer multipliers to an ingot's quality index, one per station. A contiguous run of stations multiplies its multipliers together. Find the largest product obtainable by any non-empty contiguous run. Multipliers may be zero or negative.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the multipliers in station order.
Output format
A single integer: the maximum product over all non-empty contiguous runs.
Constraints
- 1 <= n <= 20
- -8 <= each multiplier <= 8
- The answer is guaranteed to fit in a signed 64-bit integer.