Maximum Product of Three Numbers

You are given a list of n integers. Your task is to choose exactly three numbers from the list and compute their product. You need to maximize the product.

Formally, if the list is denoted as \(a_1, a_2, \dots, a_n\), find three indices \(i, j, k\) with \(i \neq j \neq k\) such that the product \(a_i \times a_j \times a_k\) is maximized. In mathematical notation, you need to find:

[ \max_{1 \leq i < j < k \leq n} {a_i \times a_j \times a_k} ]

The input list may contain positive, negative, and zero values. Consider carefully the impact of negative numbers when computing the product.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains a single integer \(n\) (\(n \ge 3\)) representing the number of elements.
• The second line contains \(n\) space-separated integers.

outputFormat

Output a single integer, which is the maximum product of any three numbers from the list. The result should be printed to standard output (stdout).

5
1 2 3 4 5

60