Maximum Product of Three Numbers

You are given an array of positive integers. Your task is to select exactly three numbers from the array such that their product is maximized.

Assume the input array is sorted in non-decreasing order as (a_1 \le a_2 \le \cdots \le a_n). The maximum product is achieved by the product (a_{n} \times a_{n-1} \times a_{n-2}).

This problem requires careful reading of the input and efficient sorting to compute the result.

inputFormat

The first line of input contains an integer (n) (with (n \ge 3)) representing the number of elements in the array. The second line contains (n) positive integers separated by spaces.

outputFormat

Output a single integer which is the maximum product of any three numbers from the array.## sample

5
1 10 2 6 5

300