Maximum Product of Three Numbers

Given a list of integers with at least three elements, your task is to find the maximum product of any three numbers in the list.

One way to approach this is by sorting the list and then computing the maximum product from either the three largest numbers or from the two smallest (which might be negative) and the largest number. Mathematically, if the sorted list is \(a_0 \le a_1 \le \dots \le a_{n-1}\), then the answer is given by:

\( \max(a_{n-1} \times a_{n-2} \times a_{n-3},\; a_0 \times a_1 \times a_{n-1}) \)

Note: The list may contain negative numbers, and the product of two negatives can be positive, so be sure to handle all scenarios including cases when all numbers are negative.

inputFormat

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

outputFormat

Output a single integer representing the maximum product of any three numbers from the list.## sample

5
1 2 3 4 5

60