P7319 "PMOI-4" Spanning Tree.

> 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.

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**.

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 one integer in one line, representing the maximum sum of weights.

[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