P7319 「PMOI-4」生成树

> 题目正解不会很难，反正很难的也必不会做，所以宁愿相信题目都是善良的。 ——command_block 《考前小贴士》 djy 出了一道生成树的题，然后发现做法假了，就把这个题改了一下，作为这场比赛的 B。

给定 $n$ 个数，第 $i$ 个数的原始权值是 $w_i$，你要按照某种顺序将这些数依次选择。 若当前是第 $i$ 次选数，选择的**原始权值**为 $k$，则其他所有**未被选过**的数的权值均加上 $(-1)^{i+k+1} \times k$。 你需要求出一种选数方案，使得选出的 $n$ 个数**最终**的**权值**和**最大**。

无

无

【样例解释】 依次选择**编号**为 $\{7,6,5,3,4,1,2\}$ 的数即可。 【数据范围】 **本题采用捆绑测试**。 - Subtask 1（20pts）：$n \le 7$。 - Subtask 2（30pts）：$n \le 10^3$。 - Subtask 3（30pts）：保证所有的 $w_i \ge 0$ 或所有的 $w_i \le 0$。 - Subtask 4（20pts）：无特殊限制。 对于 $100\%$ 的数据满足，$1 \le n \le 10^5,-10^9 \le w \le 10^9$。