题目描述

$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$ $A_1$ $A_2$ $...$ $A_N$

输出格式

$B_1\ +\ B_2\ +\ ...\ +\ B_N$ の最大値を出力せよ。

题目大意

给定一列数字 $A_1,A_2,A_3,\cdots,A_{n-1},A_n$

你可以进行若干次操作。

对于每次操作：选择 $i \in [1,n-1]$,并且吧 $A_i,A_{i-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$

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

提示

制約

• 入力は全て整数である。
• $2\ \leq\ N\ \leq\ 10^5$
• $-10^9\ \leq\ A_i\ \leq\ 10^9$

Sample Explanation 1

次のように操作を行うと、$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$ に変化する。

Sample Explanation 3

出力が $32$ ビット整数型に収まらない場合があります。