Swedish Heroes
Contest: Codeforces Round 676 (Div. 2)
Difficulty rating: 2700
Tags: brute force, dp, implementation

While playing yet another strategy game, Mans has recruited $$$n$$$ Swedish heroes, 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?

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Suitable list of operations for the first sample:

$$$[5, 6, 7, 8] \rightarrow [-11, 7, 8] \rightarrow [-11, -15] \rightarrow [26]$$$

Example input:
4
5 6 7 8

Example output:
26

Example input:
5
4 -5 9 -2 1

Example output:
15

Editorial:
Hint:
The problem gives us an array and we have to come up with an achievable sequence of pluses and minuses such that summing the numbers after applying the signs we get the largest sum. Intuitively we can probably assign + to most positive numbers and — to most negative numbers somehow, but we should investigate exactly which are possible.
Sneaky corner case:
Before you try to find patterns you should observe that there is one case that is impossible to reach. You cannot assign alternating + and — to the array, like +-+-+-+- or -+-+-+-+. The reason is very simple, the very first thing you do is apply the operation on two consecutive numbers and make them both –, and whenever you apply further operations on the both of them they remain the same sign. In the end we decided to give this in the samples but we know from testing many would miss this case.
Solution:
n = the length of the array.
m = the number of elements we multiply by -1 in the solution (put — in front of them).
p = the number of elements we do not multiply by -1 in the solution (put + in front of them).
The mysterious pattern is as follows: (n+m) So yes, for n=7 for example we can put 3 minus signs anywhere, like ++–+-+, or 6 minus signs like –+—- or full plus signs +++++++. We can arrange the pluses and minuses however we want as long as there are 2 consecutive equal signs and (n+m) The solution now simply requires us to sort the array and multiply by -1 each number one by one and when (n+m) Proof for the pattern:  The proof can be done via induction, but I will try to explain why this happens. Suppose your solution looks like +–+—+. What we need to do is to split into two substrings such that their negation is achievable and we are done, they will concatenate and reverse each sign. So we can split into (+–) and (+—+) and notice that their negations are (-++) and (-+++-) which are achievable ((n+m)