Description

给定 $n$ 个数，第 $i$ 个数的原始权值是 $w_i$，你要按照某种顺序将这些数依次选择。

若当前是第 $i$ 次选数，选择的原始权值为 $k$，则其他所有未被选过的数的权值均加上 $(-1)^{i+k+1} \times k$。

你需要求出一种选数方案，使得选出的 $n$ 个数最终的权值和最大。

Input Format

第一行一个正整数 $n$。

第二行 $n$ 个整数 $w_i$，表示第 $i$ 个数的权值。

Output Format

一行一个整数，表示最大权值和。

7
1 -1 -2 2 -3 3 4

66

Hint

【样例解释】

依次选择编号为 $\{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$。