Maximum Product of Three Numbers

You are given an array of n integers, where n ≥ 3. Your task is to select three distinct elements from the array such that their product is maximized. Mathematically, if the sorted array is represented as \(a_1 \le a_2 \le \dots \le a_n\), then the answer is given by:

\[ \max\{a_n \cdot a_{n-1} \cdot a_{n-2},\; a_1 \cdot a_2 \cdot a_n\} \]

Note that the product may involve negative numbers, which may result in a greater product when multiplied appropriately.

inputFormat

The first line contains a single integer n (n ≥ 3) which represents the number of integers in the array. The second line contains n space-separated integers.

outputFormat

Output a single integer — the maximum product of any three distinct numbers from the array.

5
10 3 5 6 20

1200