Maximum Product of Three Numbers

Given an array of integers, your task is to compute the maximum product that can be obtained by multiplying any three numbers from the array. The array may contain both positive and negative numbers, and it is guaranteed that the array contains at least three numbers.

After sorting the array, the maximum product can be found by taking the product of the three largest numbers or, alternatively, the product of the two smallest numbers (which may be negative) and the largest number. In mathematical notation, the answer is computed as:

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

where \(a_1, a_2, \dots, a_n\) are the sorted elements of the array.

inputFormat

The input is given via standard input (stdin) on a single line. The first integer represents the number of elements \(n\) (with \(n \ge 3\)), followed by \(n\) space-separated integers representing the array.

outputFormat

Output a single integer — the maximum product of any three numbers from the input array. The output should be written to standard output (stdout).

6 1 10 2 6 5 3

300