题目描述

源老师想到了一个绝妙的问题，问题是这样的：

给你 $n$ 个数字，$a_1,a_2,\cdots,a_n$。你可以执行以下操作无数次，当然也可以一次都不执行。

• 每次操作，选择一个下标 $i$，其中 $1\leq i\leq n-1$，然后将 $a_i,a_{i+1}$ 这两个数字分别乘以 $-1$。简单来说就是相邻两个数字正数变负数，负数变正数，$0$ 不变。

问你在操作以后，序列 $a$ 的总和最大可能是多少？即 $a_1+a_2+\cdots+a_n$ 的最大值。

输入格式

第一行输入一个整数 $n$

第二行输入 $n$ 个空格隔开的整数 $a_1,a_2,\cdots,a_n$

输出格式

输出一个整数代表答案。

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

样例 1 解释

• 第一次操作：选择 $i=1$ 执行，此时 $a_1\times -1=10,a_2\times -1=-5$，最终序列变为 10 -5 -4
• 第二次操作：选择 $i=2$ 执行，此时 $a_2\times -1=5,a_3\times -1=4$，最终序列变为 10 5 4

因此答案为 $10+5+4=19$

数据范围

对于 $20\%$ 的数据满足

• $2\ \leq\ n\ \leq\ 20$
• $-10^9\ \leq\ a_i\ \leq\ 10^9$

对于 $100\%$ 的数据满足

• $2\ \leq\ n\ \leq\ 10^5$
• $-10^9\ \leq\ a_i\ \leq\ 10^9$