Sequence Score
Time limit2sMemory limit128 MB
Given n integers, pair up some of them (each element used at most once) to maximize the sum of chosen singles plus products of chosen pairs.
Problem
You are given a sequence of n integers. In one operation, you may remove one integer from the sequence, or remove two distinct integers together.
If you remove one integer, that integer is added to the score. If you remove two integers together, their product is added to the score. Repeat operations until no integers remain, and find the maximum possible total score.
For instance, if the sequence is -1, 5, -3, 5, 1, you can remove 1 alone, then remove 5 and 5 together, then remove -1 and -3 together. The scores are 1, 25, and 3, so the total score is 29.
Input
The first line contains an integer n. (1 ≤ n ≤ 100,000)
Each of the next n lines contains one integer in the sequence. The absolute value of each integer is at most 1,000,000.
Output
Print the maximum total score that can be obtained.