Maximum Product with Even Number of Negative Numbers

You are given an array of integers. Your task is to compute the maximum product of a non-empty subsequence of the array with an even number of negative numbers. Note that a subsequence is not necessarily contiguous.

Important details:

• Zero values in the array do not contribute to the product and should be ignored.
• If after ignoring zeros and applying the even-negative condition no number remains, the product is defined to be 1.

Examples:

• For the array [1, -2, 3, 4, -5], the maximum product is 120.
• For the array [-1, -2, -3, 0], the maximum product is 6.
• For the array [1, -1], the maximum product is 1.

Implement your solution to read input from stdin and output the result to stdout.

inputFormat

The first line contains an integer n, the number of elements in the array. The second line contains n integers separated by spaces.

For example:

5
1 -2 3 4 -5

outputFormat

Output a single integer, which is the maximum product of a non-empty subsequence that contains an even number of negative numbers.

## sample

5
1 -2 3 4 -5

120