Maximum Product of Three Numbers

You are given an array of integers. Your task is to select exactly three numbers from the array (they may be the same in value but must come from different indices) and compute the product. The goal is to maximize this product. It is possible that the array contains negative numbers, so note that the maximum product can sometimes be obtained by multiplying two negative numbers and a positive number.

In mathematical terms, if the sorted array is \(a_1 \leq a_2 \leq \ldots \leq a_n\), then the maximum product is given by: \[ \max\left(a_{n} \times a_{n-1} \times a_{n-2},\,a_{1} \times a_{2} \times a_{n}\right) \]

You need to write a program that reads the input from stdin and prints the result to stdout.

inputFormat

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

outputFormat

Output a single integer, which is the maximum product of any three numbers from the array.

5
1 2 3 4 5

60