Highest Product of Three

Given an array of integers, your task is to determine the highest product obtained by multiplying any three distinct numbers in the array.

You can prove that the maximum product is equal to:

$$\max\left(a_{n-3}\times a_{n-2}\times a_{n-1},\; a_{0}\times a_{1}\times a_{n-1}\right)$$

where the array is first sorted as \(a_0 \leq a_1 \leq \cdots \leq a_{n-1}\). Use this observation to design an efficient solution.

inputFormat

The input consists of two lines. The first line contains an integer (n) that denotes the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output a single integer which is the highest product of any three numbers from the array.## sample

6
1 10 2 6 5 3

300