Maximum Sum of Products

You are given an array of integers. Your task is to group the integers into pairs in such a way that the sum of the products of each pair is maximized. Formally, if the array has n elements, where \(n \equiv 0 \pmod{2}\), then you must form \(\frac{n}{2}\) pairs \((a_{1}, a_{2}), (a_{3}, a_{4}), \ldots, (a_{n-1}, a_{n})\) such that the value:

[ S = \sum_{i=1}^{n/2} a_{2i-1} \times a_{2i} ]

is maximized. If the number of integers is odd, output the string "Invalid input".

Note: A greedy strategy by first sorting the array in descending order and then pairing adjacent elements yields the desired maximum sum.

inputFormat

The input is read from standard input (stdin) and consists of:

1. An integer n representing the number of elements.
2. A line containing n space-separated integers.

Constraints: It is expected that n is even. If n is odd, the output should be "Invalid input".

outputFormat

Output the maximum sum of products obtained by pairing the array elements after sorting them in descending order. If the input is invalid (i.e. n is odd), output the string "Invalid input".

4
1 3 2 1

7