Background

The intended solution should not be very hard. Anyway, if it is really hard, we definitely cannot solve it. So we would rather believe that all problems are kind.

— command_block, "Exam Tips"

djy made a spanning tree problem, then found the solution was wrong, so he modified it and used it as Problem B of this contest.

Problem Description

Given $n$ numbers, the original weight of the $i$-th number is $w_i$. You need to choose these numbers one by one in some order.

Suppose it is currently the $i$-th selection, and the chosen number has original weight $k$. Then the weights of all other numbers that have not been chosen will each increase by $(-1)^{i+k+1} \times k$.

You need to find a selection plan such that the sum of the final weights of the $n$ chosen numbers is maximized.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers $w_i$, representing the weight of the $i$-th number.

Output Format

Output one integer in one line, representing the maximum sum of weights.

7
1 -1 -2 2 -3 3 4

66

Hint

[Sample Explanation]

Choosing the numbers with indices $\{7,6,5,3,4,1,2\}$ in order works.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (20pts): $n \le 7$.
• Subtask 2 (30pts): $n \le 10^3$.
• Subtask 3 (30pts): It is guaranteed that either all $w_i \ge 0$ or all $w_i \le 0$.
• Subtask 4 (20pts): No special constraints.

For $100\%$ of the testdata, $1 \le n \le 10^5, -10^9 \le w \le 10^9$.

Translated by ChatGPT 5