Maximum Product Subset

You are given an integer array, and your task is to find the maximum product of any non-empty subset of its elements.

The challenge is to select a subset, which can be any combination of the elements (but cannot be empty), such that the product of the chosen numbers is maximized. Note that the array may contain positive numbers, negative numbers, and zeros.

Important details:

• If the array consists of a single element, the answer is that element.
• If all elements are zero, then the answer is 0.
• When there is an odd number of negative numbers, you might want to exclude the negative number with the smallest absolute value (i.e. the maximum negative) to yield a better product, except in special cases where excluding it might leave only zeros.

The final answer is an integer. If there are multiple optimal subsets, you only need to output the maximum product value.

Mathematical Formulation:

Given an array \(A = [a_1, a_2, \dots, a_n]\), find \(\max\prod_{i \in S} a_i\) over all non-empty subsets \(S \subseteq \{1,2,\dots,n\}\).

inputFormat

The first line contains a single integer \(n\), denoting the number of elements in the array.

The second line contains \(n\) space-separated integers representing the elements of the array.

You should read the input from standard input (stdin).

outputFormat

Output a single integer — the maximum product of any non-empty subset of the array's elements. Write the output to standard output (stdout).

## sample

3
1 2 3

6

</p>