Maximum Product of Three Numbers

Given an array of integers, your task is to find the maximum product of any three numbers from the array. This means you need to pick three numbers \(a, b, c\) from the array such that the product \(a \times b \times c\) is maximized.

When the array is sorted as \(a_1 \leq a_2 \leq \cdots \leq a_n\), the maximum product can be obtained by comparing the product of the three largest numbers and the product of the two smallest (possibly negative) numbers with the largest number. That is, you need to compute:

$$ \max(a_{n-2}\times a_{n-1}\times a_n,\; a_1\times a_2\times a_n) $$

and output the result.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (\(3 \leq n \leq 10^5\)), representing the number of integers in the array.
• The second line contains \(n\) space-separated integers \(x_i\) (\(-10^3 \leq x_i \leq 10^3\)).

outputFormat

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

6
1 10 2 6 5 3

300