Sequence Score

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.

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.

Print the maximum total score that can be obtained.