Highest Product of Three

You are given a list of n integers. Your task is to compute the maximum product that can be obtained by multiplying exactly three distinct numbers from the list.

The product can be computed from either:

• The three largest integers in the list, or
• The two smallest (possibly negative) integers and the largest integer.

In mathematical terms, if the sorted list 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}\} \]

It is guaranteed that the list contains at least three integers.

inputFormat

The first line contains an integer n (n \(\geq 3\)), 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 distinct integers from the list.

## sample

4
1 2 3 4

24