Maximum Product Subsequence

You are given a sequence of n integers. Your task is to select a non-empty subsequence such that the product of its elements is as large as possible.

Formally, if the sequence is \(a_1, a_2, \ldots, a_n\), you need to choose a subset of indices \(I \subseteq \{1,2,\ldots,n\}\) with \(I \neq \emptyset\) so that the product \(\prod_{i \in I} a_i\) is maximized.

Note: A subsequence here is defined as any subset of the elements (order is not important), and you are allowed to choose a single element as well.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the sequence. The second line contains \(n\) space-separated integers representing the sequence.

For example:

3
0 -1 3

outputFormat

Output a single integer, the maximum product obtained by selecting a non-empty subsequence of the given sequence.

For the sample input above, the output is:

3

## sample

3
0 -1 3

3