Maximum Product of Three Numbers

You are given a list of n integers. Your task is to compute the maximum product you can obtain by multiplying any three distinct numbers from the list. This problem requires careful consideration of negative numbers since the product of two negatives yields a positive. The answer can be computed by either taking the product of the three largest numbers, or the product of the two smallest (possibly negative) numbers and the largest number.

Mathematical formulation:

Given an array \( a_1, a_2, \dots, a_n \), find \[ \max\{ a_i \cdot a_j \cdot a_k : 1 \le i < j < k \le n \}\ \]

where the product is taken over any three distinct indices.

inputFormat

The input is given in two lines.

• The first line contains an integer n (with n ≥ 3), the number of elements in the list.
• The second line contains n space-separated integers.

outputFormat

Output a single integer, which is the maximum product obtainable by multiplying any three distinct numbers from the list.

6
1 10 2 6 5 3

300