Maximum Product of Three Numbers

Given an array of at least three integers, your task is to compute the maximum product of any three numbers from the array. The maximum product can be achieved either by multiplying the three largest numbers or by multiplying the largest number with the two smallest numbers (since negative numbers can produce a larger product when multiplied together).

Formally, if we denote the three largest numbers by \(max1, max2, max3\) and the two smallest numbers by \(min1, min2\), then the answer is:

$$ \max(max1 \times max2 \times max3,\; max1 \times min1 \times min2) $$

You are required to read the input from stdin and output the result to stdout.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (with \(n \ge 3\)), representing the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the maximum product of any three numbers from the array. The result should be printed on stdout.

## sample

4
1 2 3 4

24

</p>