Swedish Heroes

题意翻译

有一个长度为 $n$ 的序列，你要进行恰好 $n-1$ 次操作，每次操作你需要选择连续的两个数 $a_i,a_{i+1}$，然后从序列中删掉这两个数，并将 $-(a_i+a_{i+1})$ 插回到原位置。你需要让所有操作结束后序列剩下的唯一一个数最大，输出这个值。

题目描述

While playing yet another strategy game, Mans has recruited $ n $ [Swedish heroes](https://www.youtube.com/watch?v=5sGOwFVUU0I), whose powers which can be represented as an array $ a $ . Unfortunately, not all of those mighty heroes were created as capable as he wanted, so that he decided to do something about it. In order to accomplish his goal, he can pick two consecutive heroes, with powers $ a_i $ and $ a_{i+1} $ , remove them and insert a hero with power $ -(a_i+a_{i+1}) $ back in the same position. For example if the array contains the elements $ [5, 6, 7, 8] $ , he can pick $ 6 $ and $ 7 $ and get $ [5, -(6+7), 8] = [5, -13, 8] $ . After he will perform this operation $ n-1 $ times, Mans will end up having only one hero. He wants his power to be as big as possible. What's the largest possible power he can achieve?

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 200000 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ) — powers of the heroes.

输出格式

Print the largest possible power he can achieve after $ n-1 $ operations.

输入输出样例

输入样例 #1

4
5 6 7 8

输出样例 #1

26

输入样例 #2

5
4 -5 9 -2 1

输出样例 #2

15

说明

Suitable list of operations for the first sample: $ [5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26] $

题意翻译

有一个长度为 $n$ 的序列，你要进行恰好 $n-1$ 次操作，每次操作你需要选择连续的两个数 $a_i,a_{i+1}$，然后从序列中删掉这两个数，并将 $-(a_i+a_{i+1})$ 插回到原位置。你需要让所有操作结束后序列剩下的唯一一个数最大，输出这个值。