AT_abc125_d [ABC125D] Flipping Signs

题目描述

有 $N$ 个整数按顺序排列，分别为 $A_1,\ A_2,\ \ldots,\ A_N$。

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

操作：选择一个满足 $1 \leq i \leq N-1$ 的整数 $i$，将 $A_i$ 和 $A_{i+1}$ 同时乘以 $-1$。

操作结束后，整数序列变为 $B_1,\ B_2,\ \ldots,\ B_N$。

请你求出 $B_1 + B_2 + \cdots + B_N$ 的最大值。

输入格式

输入以如下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

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

样例 1

输入

3
-10 5 -4

输出

19

样例 2

输入

5
10 -4 -8 -11 3

输出

30

样例 3

输入

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$

样例解释 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$。

样例解释 3

输出结果可能无法用 $32$ 位整数类型表示。

由 ChatGPT 4.1 翻译