Maximum Product of Three Numbers

You are given an array of n integers (with n ≥ 3). Your task is to determine the maximum product obtained by multiplying any three distinct numbers in the array.

The answer can be achieved either by multiplying the three largest numbers or by multiplying the two smallest (which might be negative) with the largest number. Formally, if the sorted array is \(a_1 \leq a_2 \leq \cdots \leq a_n\), then the maximum product is:

\[ \max(a_{n} \times a_{n-1} \times a_{n-2},\ a_1 \times a_2 \times a_{n}) \]

Read the array from the standard input and print the maximum product on the standard output.

inputFormat

The first line of input contains a single integer n (n ≥ 3), which is the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output a single integer, which is the maximum product of any three integers from the array.

## sample

5
1 10 -5 1 -100

5000