Maximum Product of Three Numbers

Given an array of integers with at least three elements, your task is to compute the maximum product that can be obtained by multiplying any three distinct numbers in the array.

You may note that the answer can be obtained either by multiplying the three largest numbers or by multiplying the two smallest (possibly negative) numbers with the largest number. In other words, if we denote the three largest numbers by \(max1, max2, max3\) and the two smallest numbers by \(min1, min2\), then the answer is given by:

\(\text{result} = \max(\,max1 \times max2 \times max3,\; min1 \times min2 \times max1\,)\)

Please write an efficient solution that reads from standard input and writes the result to standard output.

inputFormat

The first line contains an integer \(n\) (with \(n \ge 3\)), representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output a single integer — the maximum product obtainable from any three numbers in the array.

## sample

6
1 10 2 6 5 3

300

</p>