Maximum Product of Three Numbers

Given a list of integers, select any three distinct numbers such that their product is maximized. The input begins with an integer n (with n ≥ 3), which indicates the number of elements. This is followed by n space-separated integers. Your task is to compute the maximum possible product obtainable by multiplying any three of these numbers.

It is possible that some of the numbers are negative. Note that the product of two negative numbers is positive, which may lead to a maximal product when combined with a positive number. You must consider all valid combinations.

The optimal solution can be achieved by sorting the list and comparing the product of the three largest numbers with the product of the two smallest numbers (which could be negative) and the largest number.

inputFormat

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

outputFormat

Output a single integer, which is the maximum product of any three distinct numbers from the list.

6
1 10 2 6 5 3

300