Largest Product of Two Distinct Elements

Given an integer array, compute the largest product of two distinct elements. The array may contain negative numbers, zeros, and positive numbers. Note that the largest product might come from either the two largest numbers or the two smallest numbers (if both are negative). Your task is to implement an algorithm that efficiently finds this product.

For example, if the input array is [1, 5, 2, 9], the correct output is 45. Similarly, for the array [3, 7, 4, 6, 9], the output should be 63.

inputFormat

The first line contains a single integer n representing the number of elements in the array.

The second line contains n space-separated integers.

outputFormat

Output a single integer representing the maximum product of two distinct elements in the array.

4
1 5 2 9

45