Maximum Product of Three Numbers

Given an array of integers, find the maximum product of any three numbers in the array. You can obtain the answer by either multiplying the three largest numbers or by multiplying the two smallest (possibly negative) numbers with the largest number. The expected time complexity is \(O(n \log n)\) or better.

For example, for the array [-10, -10, 5, 2], the maximum product is 500.

inputFormat

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

outputFormat

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

3
1 2 3

6