翻转符号

题目描述

$N$ 个整数排成一列，依次为 $A_1, A_2, ..., A_N$。

你可以对这个整数序列进行任意次以下操作。

操作：选择满足 $1 \le i \le N-1$ 的整数 $i$，将 $A_i$ 和 $A_{i+1}$ 分别乘以 $-1$。

设操作结束后的整数序列为 $B_1, B_2, ..., B_N$。

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

输入格式

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

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

输出格式

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

样例

3
-10 5 -4

19

按如下方式操作后，$B_1 = 10, B_2 = 5, B_3 = 4$，此时 $B_1 + B_2 + B_3 = 10 + 5 + 4 = 19$ 是最大值。

• 选择 $i = 1$。操作后整数序列变为 $10, -5, -4$。
• 选择 $i = 2$。操作后整数序列变为 $10, 5, 4$。

5
10 -4 -8 -11 3

30

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

10000000000

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

数据范围

• 输入均为整数
• $2 \le N \le 10^5$
• $-10^9 \le A_i \le 10^9$