Maximum Product of Three Numbers

In this problem, you are given an array of integers. Your task is to compute the maximum product that can be obtained by multiplying any three distinct numbers from the array. Note that negative numbers are allowed, and because the product of two negative numbers is positive, it is important to consider both the three largest numbers and the combination of the two smallest (possibly negative) numbers with the largest number. The mathematical comparison can be expressed in ( \max(a_n \cdot a_{n-1} \cdot a_{n-2},\ a_1 \cdot a_2 \cdot a_n) ) where the array is sorted in non-decreasing order.

inputFormat

The input consists of two lines. The first line contains an integer ( n ) (with ( n \geq 3 )) representing the number of elements in the array. The second line contains ( n ) integers separated by spaces which represent the elements of the array.

outputFormat

Output a single integer, the maximum product of any three distinct integers from the array.## sample

6
1 10 2 6 5 3

300