D - 翻转符号

得分：$400$ 分

问题描述

有 $N$ 个整数，$A_1, A_2, ..., A_N$，按照这个顺序排列。

你可以对这个整数序列进行以下操作：

操作：选择满足 $1 \leq i \leq N-1$ 的整数 $i$。令 $A_i$ 和 $A_{i+1}$ 同时乘以 $-1$。

令 $B_1, B_2, ..., B_N$ 为经过操作后的整数序列。

求 $B_1 + B_2 + ... + B_N$ 的最大可能值。

约束

• 输入的所有值均为整数。
• $2 \leq N \leq 10^5$
• $-10^9 \leq A_i \leq 10^9$

输入

输入以以下格式从标准输入给出：

$N$

$A_1$ $A_2$ $...$ $A_N$

输出

输出 $B_1 + B_2 + ... + B_N$ 的最大可能值。

3
-10 5 -4

19

如果按照以下方式进行操作：

• 选择 $i=1$，将序列变为 $10, -5, -4$。
• 选择 $i=2$，将序列变为 $10, 5, 4$。

我们得到 $B_1 = 10, B_2 = 5, B_3 = 4$。这里的和 $B_1 + B_2 + B_3 = 10 + 5 + 4 = 19$ 是最大可能的结果。

5
10 -4 -8 -11 3

30

11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000

10000000000

输出可能不适合 $32$ 位整数类型。