Maximum Product of Three Numbers

Given a list of integers, find the maximum product of any three integers in the list. It is guaranteed that the list contains at least three numbers, and the numbers may be positive, negative, or zero. In some cases, the product of the two smallest numbers (which might be negative) and the largest number may exceed the product of the three largest numbers.

Formally, if the sorted array is \(a_1 \le a_2 \le \dots \le a_n\), the answer is computed as:

$$\max\left(a_1 \times a_2 \times a_n,\; a_{n-2} \times a_{n-1} \times a_n\right)$$

inputFormat

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

outputFormat

Output a single integer which is the maximum product of any three of the given integers.

## sample

5
1 2 3 4 5

60

</p>