Highest Product of Three

Given an array of integers, your task is to compute the highest product you can obtain by multiplying exactly three of the integers. The answer will be the maximum of either:

• The product of the three largest numbers.
• The product of the two smallest numbers (which could be negative) and the largest number.

This can be mathematically formulated as:

\( \text{result} = \max\{a_{n-1} \times a_{n-2} \times a_{n-3},\, a_0 \times a_1 \times a_{n-1}\} \)

where the array a is sorted in non-decreasing order.

You can assume that the input array has at least three integers.

inputFormat

The first line contains an integer n (n \ge 3), the number of integers in the array. The second line contains n space-separated integers.

Example:

4
1 2 3 4

outputFormat

Output a single integer which is the maximum product obtained by multiplying three integers from the array.

Example:

24

## sample

4
1 2 3 4

24