题目描述

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

输入

第一行一个整数$N$,表示序列的个数

第二行$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位整数类型。

$2 \leq N \leq 10^5$

$-10^9 \leq A_i \leq 10^9$