Maximum Product of Three Numbers

Given an array of integers, your task is to determine the maximum product that can be obtained by multiplying any three distinct numbers from the array. The product of three numbers, \(a\), \(b\), and \(c\), is defined as \(a \times b \times c\). Notice that the array may contain negative numbers. Therefore, the answer can be either the product of the three largest numbers or the product of the two smallest (possibly negative) numbers and the largest number.

The input starts with an integer \(n\) (with \(n \ge 3\)) representing the number of elements, followed by \(n\) space-separated integers. Output the maximum product as a single integer.

inputFormat

The first line contains an integer (n) ((n \ge 3)). The second line contains (n) space-separated integers.

outputFormat

Print a single integer — the maximum product obtained by multiplying any three numbers from the array.## sample

6
1 10 2 6 5 3

300