翻转

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。序列中保证至少有一个正数和至少一个负数。

你可以选择若干个整数 $i$（$1\le i<n$），并对每个被选择的 $i$ 执行一次操作：将 $a_i$ 和 $a_{i+1}$ 同时乘以 $-1$。

但是任意两个被选择的位置不能相邻。也就是说，如果选择了 $i$，就不能选择 $i-1$ 或 $i+1$。因此每个数最多会参与一次翻转。

请你求操作结束后，序列元素和的最大可能值。可以不进行任何操作。

输入格式

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

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示最大可能的元素和。

样例 1

4
-5 2 -4 7

6

选择 $i=1$，序列变为 $5,-2,-4,7$，元素和为 $6$。可以证明这是最大值。

样例 2

见下发文件：flip2.in 与 flip2.out。

选择 $i=1$ 和 $i=3$，序列变为 $8,-3,10,-4,-2,7$，元素和为 $16$。

数据范围

对于 $100\%$ 的数据，$2\le n\le 2\times10^5$，$-10^9\le a_i\le10^9$，$a_i\ne0$。

保证序列中至少存在一个正数和至少一个负数。

本题沿用原题的文件名 flip1.in 和 flip1.out。

更多样例

以下 2 组样例取自原题附件：

• flip-down1.in / flip-down1.out
• flip-down2.in / flip-down2.out