题目描述

给定一列数字 $A_1,A_2,A_3,\cdots,A_{n-1},A_n$，你可以进行若干次操作。

对于每次操作：选择 $i \in [1,n-1]$，并且把 $A_i,A_{i-1}$ 均乘以 $-1$。我们设最后得到的序列为 $B_1,B_2,B_3\cdots,B_n$，求 $\sum_{i=1}^n B_i$ 的最大值。

其中 $2\leq N\leq 10^5$，$-10^9\leq A_i\leq 10^9$。

输入格式

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

第二行 $N$ 和整数 $A_i$。

输出格式

$\sum_{i=1}^n B_i$ 的最大值。

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