Maximum Product of Three Numbers

You are given an array of integers. Your task is to find three numbers in the array such that their product is maximized and print this maximum product.

To solve the problem, note that the optimal product can be achieved in one of the following ways:

• Product of the three largest numbers: \(product1 = a_{n-2} \times a_{n-1} \times a_{n}\).
• Product of the two smallest numbers (which might be negative) and the largest number: \(product2 = a_{1} \times a_{2} \times a_{n}\).

The answer is \(\max(product1,\, product2)\).

Input: The first line contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) integers separated by spaces.

Output: A single integer which is the maximum product of any three numbers from the array.

inputFormat

Input is read from standard input. The first line contains an integer (n) ((n \ge 3)). The second line contains (n) space-separated integers.

outputFormat

Output the maximum product of any three numbers in the array to standard output.## sample

3
1 2 3

6