Maximum Product Triplet

Given an array of integers, your task is to compute the maximum product of any triplet (three numbers) selected from the array. In other words, you need to choose three distinct integers a, b, and c from the array such that the product \(a \times b \times c\) is maximized.

Note that the array may contain negative numbers. Recall that the product of two negative numbers is positive, which might lead to a larger overall product when combined with a large positive number. Hence, the maximum product is either:

• The product of the three largest numbers, or
• The product of the two smallest numbers (which could be negative) and the largest number.

Your algorithm should consider both possibilities and output the maximum product possible.

inputFormat

The input consists of two lines. The first line contains an integer (n) (where (3 \leq n \leq 10^5)), representing the number of elements in the array. The second line contains (n) space-separated integers, which may be negative, zero, or positive.

outputFormat

Output a single integer, which is the maximum product that can be obtained by multiplying any three distinct numbers from the array.## sample

5
1 4 3 -6 -7

168