Highest Product

You are given a list of integers and your task is to find the highest product that can be made by multiplying any three of them.

The problem can be formally stated as follows:

Given an array of integers (a_1, a_2, \dots, a_n) where (n \geq 3), find the maximum value of (a_i \times a_j \times a_k) for any three distinct indices (i, j, k). A key observation is that the maximum product is either produced by the product of the three largest numbers or by the product of the two smallest (which may be negative) and the largest number.

For example, for the array [1, 10, 2, 6, 5, 3], the highest product is (300) (i.e. (10 \times 6 \times 5)).

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (n) (where (n \geq 3)) representing the number of integers. The second line contains (n) space-separated integers.

outputFormat

Output a single integer to standard output (stdout) which is the highest product that can be obtained by multiplying any three integers from the list.## sample

6
1 10 2 6 5 3

300