Maximum Product of Three Numbers

You are given an array of (n) integers. Your task is to compute the maximum product obtained by multiplying any three numbers from the array. In other words, if the sorted array is (a_0, a_1, \dots, a_{n-1}), then the answer can be computed as [ \max{a_0 \times a_1 \times a_{n-1},; a_{n-3} \times a_{n-2} \times a_{n-1}} ] Note that the array may contain positive, negative, and zero values. It is guaranteed that (n \ge 3).

inputFormat

Input is given via standard input. The first line contains an integer (n) ((n \ge 3)), representing the number of integers in the array. The second line contains (n) space-separated integers.

outputFormat

Output the maximum product of any three numbers from the array via standard output.## sample

6
1 4 3 -6 -7 0

168