Maximum Product of Three Numbers

Given an array of integers, your task is to compute the maximum product obtainable by multiplying any three distinct numbers from the array. This can be achieved by either taking the product of the three largest numbers, or in cases where negative numbers are included, by multiplying the two smallest (possibly negative) numbers with the largest number.

In mathematical terms, if the sorted array is \(a_1 \le a_2 \le \dots \le a_n\), the answer is given by

\(\max(a_{n} \times a_{n-1} \times a_{n-2},\; a_1 \times a_2 \times a_{n})\).

inputFormat

The input consists of two lines. The first line contains an integer (n) (with (n \ge 3)), representing the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Print a single integer which is the maximum product of any three numbers from the array.## sample

4
1 2 3 4

24