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-----

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-----

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


-----Examples-----
Input
4
5 6 7 8

Output
26

Input
5
4 -5 9 -2 1

Output
15



-----Note-----

Suitable list of operations for the first sample:

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

Difficulty: interview

Starter code:

Solutions:
N,x,y,z,v,w=input(),-9e9,-9e9,-9e9,0,1
for A in map(int,input().split()):x,y,z,v,w=max(z+A,y-A),max(x+A,z-A),max(y+A,x-A,v-w*A),v+w*A,-w
print([v,y][N>'1'])

N,x,y,z,v,w=input(),-9e9,-9e9,-9e9,0,1
for A in map(int,input().split()):x,y,z,v,w=max(z+A,y-A),max(x+A,z-A),max(y+A,x-A,v-w*A),v+w*A,-w
print([v,y][N>'1'])

N,x,y,z,v,w=input(),-9e9,-9e9,-9e9,0,1
for A in map(int,input().split()):x,y,z,v,w=max(z+A,y-A),max(x+A,z-A),max(y+A,x-A,v-w*A),v+w*A,-w
print([v,y][N>'1'])


from heapq import nsmallest
from math import inf as _inf
import sys as _sys


def main():
    n, = _read_ints()
    a = tuple(_read_ints())
    result = find_max_power_can_make(a)
    print(result)


def _read_line():
    result = _sys.stdin.readline()
    assert result[-1] == "\n"
    return result[:-1]


def _read_ints():
    return list(map(int, _read_line().split()))


def find_max_power_can_make(heroes_powers):
    heroes_powers = tuple(heroes_powers)
    assert heroes_powers
    
    abs_powers_sum = sum(map(abs, heroes_powers))
    
    if len(heroes_powers) <= 9:
        return _compute_using_brute_force(heroes_powers)
    
    zeros_n = heroes_powers.count(0)
    if zeros_n >= 2:
        return abs_powers_sum
    assert zeros_n <= 1
    
    n = len(heroes_powers)
    if n % 3 == 1 % 3:
        can_invert_mod_3 = 0
    elif n % 3 == 2 % 3:
        can_invert_mod_3 = 2
    else:
        assert n % 3 == 3 % 3
        can_invert_mod_3 = 1
    
    result = -_inf
    
    for is_zero_positive in (False, True):
        
        if zeros_n == 0 or is_zero_positive:
            signs = [1 if x >= 0 else -1 for x in heroes_powers]
        else:
            signs = [1 if x > 0 else -1 for x in heroes_powers]
        
        negative_n = signs.count(-1)
        have_pair_of_same = any(signs[i] == signs[i + 1] for i in range(len(signs) - 1))
        is_trivial = not (not have_pair_of_same and negative_n % 3 == can_invert_mod_3)
        
        if is_trivial:
            if negative_n % 3 == can_invert_mod_3:
                result = max(result, abs_powers_sum)
                continue
            negative_to_inverse_1 = negative_n
            while negative_to_inverse_1 % 3 != can_invert_mod_3:
                negative_to_inverse_1 -= 1
            negative_to_inverse_2 = negative_to_inverse_1 + 3
        else:
            negative_to_inverse_1 = negative_n - 3
            negative_to_inverse_2 = negative_n + 3
            min_pos = max(
                heroes_powers,
                key=lambda x: (x >= 0 if is_zero_positive else x > 0, -abs(x))
            )
            max_neg = max(
                heroes_powers,
                key=lambda x: (x < 0 if is_zero_positive else x <= 0, x)
            )
            result = max(result, abs_powers_sum - 2 * abs(min_pos) - 2 * abs(max_neg))
        
        if negative_to_inverse_1 >= 0:
            negative_to_remain_n = negative_n - negative_to_inverse_1
            assert negative_to_remain_n > 0
            negative_powers = tuple([x for x in heroes_powers if (x < 0 if is_zero_positive else x <= 0)])
            if negative_to_remain_n <= len(negative_powers):
                negative_to_remain = nsmallest(
                    negative_to_remain_n, negative_powers, key=abs
                )
                result = max(result, abs_powers_sum - 2 * abs(sum(negative_to_remain)))
        
        if negative_to_inverse_2 <= n:
            positive_to_inverse_n = negative_to_inverse_2 - negative_n
            assert positive_to_inverse_n > 0
            positive_powers = tuple([x for x in heroes_powers if (x >= 0 if is_zero_positive else x > 0)])
            if positive_to_inverse_n <= len(positive_powers):
                positive_to_inverse = nsmallest(
                    positive_to_inverse_n, positive_powers, key=abs
                )
                result = max(result, abs_powers_sum - 2 * sum(positive_to_inverse))
    
    return result


def _compute_using_brute_force(seq):
    n = len(seq)
    if n == 1:
        return seq[0]
    return max(
        _compute_using_brute_force(seq[:i] + (-(seq[i] + seq[i+1]),) + seq[i+2:])
        for i in range(n - 1)
    )


def __starting_point():
    main()

__starting_point()

N,x,y,z,v,w=input(),-9e9,-9e9,-9e9,0,1
for A in map(int,input().split()):x,y,z,v,w=max(z+A,y-A),max(x+A,z-A),max(y+A,x-A,v-w*A),v+w*A,-w
print([v,y][N>'1'])



from heapq import nsmallest
from math import inf as _inf
import sys as _sys


def main():
    n, = _read_ints()
    a = tuple(_read_ints())
    result = find_max_power_can_make(a)
    print(result)


def _read_line():
    result = _sys.stdin.readline()
    assert result[-1] == "\n"
    return result[:-1]


def _read_ints():
    return map(int, _read_line().split())


def find_max_power_can_make(heroes_powers):
    heroes_powers = tuple(heroes_powers)
    assert heroes_powers

    abs_powers_sum = sum(map(abs, heroes_powers))

    if len(heroes_powers) <= 9:
        return _compute_using_brute_force(heroes_powers)

    zeros_n = heroes_powers.count(0)
    if zeros_n >= 2:
        return abs_powers_sum
    assert zeros_n <= 1

    n = len(heroes_powers)
    if n % 3 == 1 % 3:
        can_invert_mod_3 = 0
    elif n % 3 == 2 % 3:
        can_invert_mod_3 = 2
    else:
        assert n % 3 == 3 % 3
        can_invert_mod_3 = 1

    result = -_inf

    for is_zero_positive in (False, True):

        if zeros_n == 0 or is_zero_positive:
            signs = [1 if x >= 0 else -1 for x in heroes_powers]
        else:
            signs = [1 if x > 0 else -1 for x in heroes_powers]

        negative_n = signs.count(-1)
        have_pair_of_same = any(signs[i] == signs[i + 1] for i in range(len(signs) - 1))
        is_trivial = not (not have_pair_of_same and negative_n % 3 == can_invert_mod_3)

        if is_trivial:
            if negative_n % 3 == can_invert_mod_3:
                result = max(result, abs_powers_sum)
                continue
            negative_to_inverse_1 = negative_n
            while negative_to_inverse_1 % 3 != can_invert_mod_3:
                negative_to_inverse_1 -= 1
            negative_to_inverse_2 = negative_to_inverse_1 + 3
        else:
            negative_to_inverse_1 = negative_n - 3
            negative_to_inverse_2 = negative_n + 3
            min_pos = max(
                heroes_powers,
                key=lambda x: (x >= 0 if is_zero_positive else x > 0, -abs(x))
            )
            max_neg = max(
                heroes_powers,
                key=lambda x: (x < 0 if is_zero_positive else x <= 0, x)
            )
            result = max(result, abs_powers_sum - 2 * abs(min_pos) - 2 * abs(max_neg))

        if negative_to_inverse_1 >= 0:
            negative_to_remain_n = negative_n - negative_to_inverse_1
            assert negative_to_remain_n > 0
            negative_powers = tuple(filter(
                lambda x: x < 0 if is_zero_positive else x <= 0, heroes_powers
            ))
            if negative_to_remain_n <= len(negative_powers):
                negative_to_remain = nsmallest(
                    negative_to_remain_n, negative_powers, key=abs
                )
                result = max(result, abs_powers_sum - 2 * abs(sum(negative_to_remain)))

        if negative_to_inverse_2 <= n:
            positive_to_inverse_n = negative_to_inverse_2 - negative_n
            assert positive_to_inverse_n > 0
            positive_powers = tuple(filter(
                lambda x: x >= 0 if is_zero_positive else x > 0, heroes_powers
            ))
            if positive_to_inverse_n <= len(positive_powers):
                positive_to_inverse = nsmallest(
                    positive_to_inverse_n, positive_powers, key=abs
                )
                result = max(result, abs_powers_sum - 2 * sum(positive_to_inverse))

    return result


def _compute_using_brute_force(seq):
    n = len(seq)
    if n == 1:
        return seq[0]
    return max(
        _compute_using_brute_force(seq[:i] + (-(seq[i] + seq[i + 1]),) + seq[i + 2:])
        for i in range(n - 1)
    )


def __starting_point():
    main()
__starting_point()

from sys import stdin

input = stdin.readline


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    # (n + number with -1 sign)%3 == 1
    # dp[i][j][k][l]: choose from a[:i], j = (n + num with -1 sign) mod 3,
    # k = whether two consecutive same sign, l =  1 if last number is + else 0
    if n == 1:
        print(max(a[0],-a[0]))
        return
    NINF = -10 ** 15
    dp = [[[[NINF] * 2 for i in range(2)] for j in range(3)] for k in range(n)]
    dp[0][n % 3][0][1] = a[0]
    dp[0][(n + 1) % 3][0][0] = -a[0]
    for i in range(n-1):
        for j in range(3):
            for k in range(2):
                for l in range(2):
                    if dp[i][j][k][l] > NINF:
                        dp[i+1][j][k or l == 1][1] = max(dp[i+1][j][k or l == 1][1], dp[i][j][k][l] + a[i+1])
                        dp[i+1][(j + 1) % 3][k or l == 0][0] = max(dp[i+1][(j + 1) % 3][k or l == 0][0],
                                                                    dp[i][j][k][l] - a[i+1])

    print(max(dp[n-1][1][1][1], dp[n-1][1][1][0]))


def __starting_point():
    solve()

__starting_point()

n = int(input())
a = list(map(int,input().split()))
INF = 10 ** 20
DP = [-INF] * 12
DP[1] = a[0]
DP[5] = -a[0]
for elem in a[1:]:
    newDP = []
    newDP.append(DP[5] + elem)
    newDP.append(DP[3] + elem)
    newDP.append(DP[4] + elem)
    newDP.append(DP[1] - elem)
    newDP.append(DP[2] - elem)
    newDP.append(DP[0] - elem)
    newDP.append(max(DP[2] + elem, DP[8] + elem, DP[11] + elem))
    newDP.append(max(DP[0] + elem, DP[6] + elem, DP[9] + elem))
    newDP.append(max(DP[1] + elem, DP[7] + elem, DP[10] + elem))
    newDP.append(max(DP[4] - elem, DP[7] - elem, DP[10] - elem))
    newDP.append(max(DP[5] - elem, DP[8] - elem, DP[11] - elem))
    newDP.append(max(DP[3] - elem, DP[6] - elem, DP[9] - elem))
    DP = newDP
if n == 1:
    print(a[0])
else:
    print(max(DP[7],DP[10]))


n = int(input())
a = list(map(int, input().split()))
if n == 1:
    print(a[0])
    return
inf = float('inf')
dp = [[[-inf, -inf, -inf] for _ in range(2)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
    for j in range(2):
        for k in range(3):
            dp[i+1][j][(k+1)%3] = max(dp[i+1][j][(k+1)%3], dp[i][j][k] + a[i])
            dp[i+1][j][(k-1)%3] = max(dp[i+1][j][(k-1)%3], dp[i][j][k] - a[i])
    if i + 1 < n:
        for k in range(3):
            dp[i+2][1][(k+2)%3] = max(dp[i+2][1][(k+2)%3], dp[i][0][k] + a[i] + a[i+1])
            dp[i+2][1][(k-2)%3] = max(dp[i+2][1][(k-2)%3], dp[i][0][k] - a[i] - a[i+1])
ans = dp[n][1][1]
print(ans)

n = int(input())
a = list(map(int, input().split()))
if n == 1:
    print(a[0])
    return
inf = 1002003004005006007
dp = [[[-inf, -inf, -inf] for _ in range(2)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
    for j in range(2):
        for k in range(3):
            dp[i+1][j][(k+1)%3] = max(dp[i+1][j][(k+1)%3], dp[i][j][k] + a[i])
            dp[i+1][j][(k-1)%3] = max(dp[i+1][j][(k-1)%3], dp[i][j][k] - a[i])
    if i + 1 < n:
        for k in range(3):
            dp[i+2][1][(k+2)%3] = max(dp[i+2][1][(k+2)%3], dp[i][0][k] + a[i] + a[i+1])
            dp[i+2][1][(k-2)%3] = max(dp[i+2][1][(k-2)%3], dp[i][0][k] - a[i] - a[i+1])
ans = dp[n][1][1]
print(ans)

N = int(input())
x, y, z, v, w = float("-inf"), float("-inf"), float("-inf"), 0, 1
for A in map(int, input().split()):
    x, y, z, v, w = max(z + A, y - A), max(x + A, z - A), \
                    max(y + A, x - A, v - w * A), v + w * A, -w
print([v, y][N > 1])

N = int(input())
a, b, c, d, e = float("-inf"), float("-inf"), float("-inf"), 0, 1
for x in map(int, input().split()):
    a, b, c, d, e = max(c + x, b - x), max(a + x, c - x), \
                    max(b + x, a - x, d - e * x), d + e * x, -e
print([d, b][N > 1])