Maximum Product of Three Numbers

Given an array of integers, your task is to select three distinct numbers from the array such that their product is maximized. Note that the array may contain both positive and negative integers; thus, two cases must be considered:

1. The product of the three largest numbers.

2. The product of the largest number and the two smallest numbers (which may be negative, and their product can be positive).

The solution should compute the value of:

\( \text{max_product} = \max(a_{n-1} \times a_{n-2} \times a_{n-3},\; a_{0} \times a_{1} \times a_{n-1}) \)

where the array is sorted in non-decreasing order and \(a_0\) and \(a_1\) are the two smallest elements, and \(a_{n-1}\), \(a_{n-2}\), \(a_{n-3}\) are the three largest elements.

inputFormat

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

outputFormat

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

5
10 3 5 6 20

1200