An amplifier chain has n stages in a row. Stage i has an integer gain multiplier g_i: positive means normal amplification, negative means the signal's phase is inverted, and zero means the stage mutes the signal completely. The chain's output for any contiguous run of stages is the PRODUCT of their gains. Find the maximum possible product over all non-empty contiguous runs of stages.
Input format
Line 1: an integer n.
Line 2: n space-separated integers g_1 ... g_n.
Output format
A single integer: the maximum product achievable by a non-empty contiguous run of stages.
Constraints
- 1 ≤ n ≤ 100000
- -20 ≤ g_i ≤ 20