You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给定一个整数数组ai，请你找出数组中乘积最大的连续子x序列（该子序列中至少包含一个数字），并返回该子数组所对应的乘积。

Format

Input

第一行为一个正整数n。 第二行为n个整数$a_i$，之间用空格隔开。

Output

最大子段积。

Samples

6
2 3 -2 4 -1 -8

48

对于100%的数据，1≤n≤50, $-20≤a_i≤20$。最大乘积不会超过$2^{63}−1$。