题目描述

黑板上有 $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$ 的最大可能值。

示例输入 1

3
-10 5 -4

示例输出 1

19

如果我们按以下方式执行操作：

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

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

示例输入 2

5
10 -4 -8 -11 3

示例输出 2

30

示例输入 3

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

示例输出 3

10000000000

输出可能超过 $32$ 位整数类型的范围。