There are N integers, A_1, A_2, ..., A_N, arranged in a row in this order.
You can perform the following operation on this integer sequence any number of times:
Operation: Choose an integer i satisfying 1 \leq i \leq N-1. Multiply both A_i and A_{i+1} by -1.
Let B_1, B_2, ..., B_N be the integer sequence after your operations.
Find the maximum possible value of B_1 + B_2 + ... + B_N.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^5
 - -10^9 \leq A_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the maximum possible value of B_1 + B_2 + ... + B_N.

-----Sample Input-----
3
-10 5 -4

-----Sample Output-----
19

If we perform the operation as follows:
 - Choose 1 as i, which changes the sequence to 10, -5, -4.
 - Choose 2 as i, which changes the sequence to 10, 5, 4.
we have B_1 = 10, B_2 = 5, B_3 = 4. The sum here, B_1 + B_2 + B_3 = 10 + 5 + 4 = 19, is the maximum possible result.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
a=list(map(int,input().split()))
count=0
ans=[]
for i in range(n):
  ans.append(abs(a[i]))
  if a[i]<0:
    count+=1

if count%2==0:
  print((sum(ans)))
else:
  print((sum(ans)-2*min(ans)))


n = int(input())
a = list(map(int, input().split()))
cnt = [1 for x in a if x < 0]
ans = 0
mini = float("inf")
for i in a:
    if i < 0:
        i *= -1
    mini = min(mini, i)
    ans += i
if sum(cnt) % 2 == 0:
    print(ans)
else:
    print(ans - mini * 2)

n = int(input())
a = list(map(int, input().split()))

ans = 0
neg = 0
zero = False
smallest = abs(a[0])

for i in range(n):
    ans += abs(a[i])

    if abs(a[i]) < smallest:
        smallest = abs(a[i])

    if a[i] == 0:
        zero = True
    elif a[i] < 0:
        neg += 1

if neg % 2 == 1 and not zero:
    print(ans-2*smallest)
else:
    print(ans)

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def S_MAP(): return list(map(str, input().split()))
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
minus = 0
plus = 0
zero = 0
ans_A = []
for a in A:
    if a < 0:
        minus += 1
    elif a > 0:
        plus += 1
    else:
        zero += 1
    ans_A.append(abs(a))

ans_A.sort()

if zero > 0:
    print((sum(ans_A)))
    return
if minus % 2 == 0:
    print((sum(ans_A)))
else:
    print((sum(ans_A[1:])-ans_A[0]))




n=int(input())
a=list(map(int,input().split()))
b=[abs(i) for i in a]
print(sum(b)-sum(i<0 for i in a)%2*min(b)*2)

n = int(input())
a = list(map(int, input().split()))

a.sort()
minus = n
for i in range(n):
  if a[i] >= 0:
    minus = i
    break

a = list(map(abs, a))
a.sort()

if minus % 2 == 0:
  print((sum(a)))
else:
  print((sum(a) - 2 * a[0]))


n=int(input())
a=list(map(int,input().split()))
count=0
for i in range(n):
    if a[i]<0:
        count+=1
if count%2==0:
    for j in range(n):
        a[j]=abs(a[j])
    print((sum(a)))
else:
    for j in range(n):
        a[j]=abs(a[j])
    print((sum(a)-2*min(a)))
    


#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    # dp[1]: flipped
    dp = [[float('inf')] * N for _ in range(2)]
    dp[0][0] = A[0]
    dp[1][0] = -A[0]
    for i, a in enumerate(A[1:], 1):
        dp[0][i] = max(dp[0][i-1]+a, dp[1][i-1]-a)
        dp[1][i] = max(dp[0][i-1]-a, dp[1][i-1]+a)
    return max(dp[0][N-2]+A[-1], dp[1][N-2]-A[-1])


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print((solve(N, A)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

N = int(input()); INF = float("inf")
A = list(map(int,input().split()))
#dp[i+1][j]: i番目まで見てj=0(i番目がそのまま),j=1(i番目が逆転)の時の最大値
dp = [[-INF]*2 for _ in range(N)]
dp[0][0] = 0
dp[0][1] = 0
dp[1][0] = A[0]+A[1]
dp[1][1] = -(A[0]+A[1])
for i in range(2,N):
  dp[i][0] = max(dp[i-1][0] + A[i], dp[i-1][1] + A[i])
  dp[i][1] = max(dp[i-1][0] - (A[i-1]*2 + A[i]), dp[i-1][1] + A[i-1]*2 - A[i])
#print(dp)
ans = max(dp[N-1])
print(ans)

n=int(input())
a=list(map(int,input().split()))

cnt=0
ans=0

for i in range(n):
    if a[i]<0:
        cnt+=1
        a[i]*=-1



if cnt%2==0:
    ans=sum(a)

else:
    ans=sum(a)-2*min(a)

print(ans)


import numpy as np

n=int(input())
A=np.array(list(map(int,input().split())))
minus = np.count_nonzero(A < 0)
A = np.abs(A)

if 0 in A or minus % 2 == 0:
  print(np.sum(A))
else:
  print(np.sum(A) - 2 * np.min(A))

N = int(input())
A = list(map(int, input().split()))

cnt = len([i for i in A if i < 0])
PA = list(map(abs, A))

if cnt % 2 == 0:
    print(sum(PA))
else:
    print(sum(PA) - min(PA) * 2)

N = int(input())
A = list(map(int, input().split()))
ans = 0
Amin = 10 ** 9 + 1
flag = 0
for i in range(N):
  if i < N-1 and A[i] < 0:
    A[i] = -A[i]
    A[i+1] = -A[i+1]
  elif i == N-1 and A[i] < 0:
    A[i] = -A[i]
    flag = -1
    
  ans += A[i]
  
  if A[i] < Amin:
    Amin = A[i]
    
print((ans + (flag * 2 * Amin)))




N = int(input())
A = list(map(int, input().split()))

souwa = 0
cnt = 0
keep = 1e10

for i in range(N):
    if A[i] < 0:
        cnt += 1
        A[i] *= (-1)

    souwa += A[i]
    keep = min(keep, A[i])

print((souwa - 2 * keep * (cnt % 2)))


#!/usr/bin/env python3

INF = 10**9 + 1

def solve(n,a):
    ans = 0
    minusCount = 0
    minimumNum = INF
    lst = []
    for i in range(n):
        if a[i] < 0:
            minusCount += 1
        ans += abs(a[i])
        minimumNum = min(minimumNum,abs(a[i]))
    if minusCount % 2 == 0:
        pass
    else:
        ans -= minimumNum*2
    return ans


def main():
    N = int(input())
    a = list(map(int,input().split()))
    print((solve(N,a)))

def __starting_point():
    main()

__starting_point()

MAX_N = 1_000_000_000


N = int(input())
A = [int(x) for x in input().split()]

cnt = 0
min_n = MAX_N
ans = 0
for a in A:
    ans += abs(a)
    if a <= 0:
        cnt += 1
    min_n = min(min_n, abs(a))
if cnt % 2 == 0:
    print(ans)
else:
    print((ans - min_n * 2))


n = int(input())
a = list(map(int,input().split()))
c = 0
for i in range(n):
    if a[i] < 0:
        c += 1
        a[i] = abs(a[i])
if c % 2 == 0:
    print(sum(a))
else:
    print(sum(a)-(min(a)*2))

N = int(input())
A = list(map(int,input().split()))

minus_cnt = 0
abs_sum = 0
min_abs_val = 1000000000
for i in range(N):
    abs_val = abs(A[i])
    abs_sum = abs_sum + abs_val
    if abs_val < min_abs_val:
        min_abs_val = abs_val
    if A[i] < 0:
        minus_cnt = minus_cnt + 1

B_max_sum = 0
if (minus_cnt % 2 == 0) or (min_abs_val == 0):
    B_max_sum = abs_sum
else:
    B_max_sum = abs_sum - min_abs_val * 2

print(B_max_sum)


n = int(input())
A =list(map(int, input().split()))

dp = [[0]*2 for _ in range(n)]
# dp[i][0]:*1
# dp[i][1]:*(-1)
for i in range(n-1):
    if i == 0:
        dp[i+1][0] += A[i]
        dp[i+1][1] += -A[i]
    else:
        dp[i+1][0] = max(dp[i][0]+A[i], dp[i][1]+(-1)*A[i])
        dp[i+1][1] = max(dp[i][0]+(-1)*A[i], dp[i][1]+A[i])
ans = max(dp[n-1][0]+A[n-1], dp[n-1][1]+(-1)*A[n-1])
print(ans)


N,A = int(input()),list(map(int,input().split()))

zero = 0
minus = 0
for i in range(N):
    if A[i]<0:minus += 1
    elif A[i]==0:
        zero=1
    A[i] = abs(A[i])

if (minus%2==0)|(zero==1):
    print(sum(A))
else:
    print(sum(A)-2*min(A))

n = int(input())
a = list(map(int, input().split()))

# 全ての値の合計を求め、負の値が偶数個であれば全ての値は非負の値にできる為、合計値を出力
# 負の値の数が奇数個の場合は1つだけが負の値になる為、この場合は最小値を負の値にして合計を出力
ans = 0
count = 0
for i in range(n):
  if a[i] < 0: count += 1 # 負の値をカウント
  a[i] = abs(a[i])
  ans += a[i] # 全ての値を足していく
if count%2 == 0: print(ans) # 負の値が偶数個であればそのまま出力
else:
  ans -= 2*min(a) # 負の値が奇数個であれば最小値の値分減らして出力
  print(ans)

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: list(map(int, INPUT().split()))
S_MAP = lambda: list(map(str, INPUT().split()))
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    neg = 0
    m = INF
    for i in range(N):
        if A[i] < 0:
            neg += 1
            A[i] = - A[i]
        m = min(m, A[i])

    if 0 in A:
        print((sum(A)))
    else:
        print((sum(A) - (2 * m)*(neg % 2)))


def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(map(int, input().split()))

s = [abs(i) for i in a]
minus = sum([1 for i in a if i < 0])
print(sum(s) if minus%2 == 0 else sum(s)-2*min(s))

import math

n = int(input())
aL = list(map(int, input().split(" ")))

mc = 0
for a in aL:
    if a < 0:
        mc += 1

aL = list([abs(x) for x in aL])

if mc % 2 == 0:
    print((sum(aL)))
else:
    print((sum(aL) - (2 * min(aL))))


import numpy as np

n = int(input())
A = np.array(list(map(int,input().split())))
minus = np.count_nonzero(A < 0)
A = np.abs(A)

if minus % 2 == 0:
  print(np.sum(A))
else:
  print(np.sum(A) - 2 * np.min(A))

# coding: UTF-8
import sys
import numpy as np
import math


n = int(input())
aList = list(map(int, input().split()))
numMinus = 0
for i in range(n):
	if aList[i] < 0:
		numMinus += 1
		aList[i] *= -1

aList.sort()

if numMinus % 2 == 0:
	print((sum(aList)))
else:
	print((sum(aList) - 2 * aList[0]))


n = int(input())
a = list(map(int, input().split()))
minus = 0
sum = 0
zero = False
minimum = abs(a[0])
for i in a:
    if i == 0:
        zero = True
    if i < 0:
        minus += 1
    minimum = min(minimum, abs(i))
    sum += abs(i)
if zero:
    print(sum)
elif minus % 2 == 0:
    print(sum)
else:
    print(sum - 2 * minimum)

import sys

def read_str(): return sys.stdin.readline().strip()
def read_int(): return int(sys.stdin.readline().strip())
def read_ints(): return list(map(int, sys.stdin.readline().strip().split()))
def read_str_split(): return list(sys.stdin.readline().strip())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))

def Main():
    N = read_int()
    A = read_int_list()
    abs_a = list(map(abs, A))
    minus_a = [v for v in A if v < 0]
    min_abs = min(abs_a)
    len_minus = len(minus_a)
    sum_abs = sum(abs_a)
    if len_minus % 2 == 0:
        print(sum_abs)
    else:
        print((sum_abs - min_abs * 2))

def __starting_point():
    Main()

__starting_point()

n=int(input())
a=list(map(int,input().split()))

c=0
for ia in a:
    if ia<0:
        c+=1
a=list(map(abs,a))

if c%2==0:
    print(sum(a))
else:
    print(sum(a)-2*min(a))

n = int(input())
a = list(map(int, input().split()))
ans = 0
count = 0
for i in range(n):
    if a[i] < 0:
        count += 1
    a[i] = abs(a[i])
    ans += a[i]
if count % 2 == 0:
    print(ans)
else:
    ans -= 2 * min(a)
    print(ans)

import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

cnt = 0
for a in A:
    if a< 0:
        cnt += 1

if cnt % 2 == 0:
    B = [abs(a) for a in A]
    ans = sum(B)
else:
    C = [abs(a) for a in A]
    C_min = min(C)
    C_min_id = C.index(C_min)

    C[C_min_id] = C[C_min_id] * (-1)
    ans = sum(C)
print(ans)


n = int(input())
A = list(map(int,input().split()))

law_ans = 0
absminA = float('inf')
for a in A:
    law_ans += abs(a)
    absminA = min(absminA, abs(a))


cnt_neg = 0

for a in A:
    if a < 0:
        cnt_neg += 1

cnt_0 = A.count(0)

if cnt_0 == 0:
    if cnt_neg%2 == 0:
        print(law_ans)
    else:
        print((law_ans-2*absminA))
else:
    print(law_ans)


n=int(input())
a=list(map(int,input().split()))

c=0
for ia in a:
    if ia<0:
        c+=1
a=list(map(abs,a))

if c%2==0:
    print(sum(a))
else:
    print(sum(a)-2*min(a))

n = input()
a = list(map(int, input().split()))
m = 0
for i in a:
  if i < 0:
    m += 1
b = list(map(abs, a))
if m % 2 == 0:
  print(sum(b))
else:
  print(sum(b) - 2*min(b))

n = int(input())
a = list(map(int,input().split()))
num = 0
mi = 10**9
for i in range(n):
    num += abs(a[i])
    if abs(mi) >= abs(a[i]):
        mi = a[i]
cnt = 0
for i in range(n):
    if a[i] < 0:
        cnt += 1
if cnt%2 == 1:
    print(num-2*abs(mi))
else:
    print(num)

n=int(input())
a=list(map(int,input().split()))
c=0#負数の数
ab=10**10#絶対値の最小
s=0#絶対値の総和
for i in range(n):
    if a[i]<0:
        c+=1
    if ab>abs(a[i]):
        ab=abs(a[i])
    s+=abs(a[i])
if c%2==0:
    print(s)
else:
    print((s-2*ab))


#!/usr/bin/env python3
n, *a = list(map(int, open(0).read().split()))
for i in range(n - 1):
    if a[i] < 0:
        a[i] *= -1
        a[i + 1] *= -1
print((sum(a) - 2 * min(abs(i) for i in a) - 2 * a[-1] if a[-1] < 0 else sum(a)))


n=int(input())
a=list(map(int,input().split()))
if 0 in a:
  print(sum(abs(i)for i in a))
else:
  pc=mc=0
  for i in range(n):
    if a[i]>0:pc+=1
    else:mc+=1
    a[i]=abs(a[i])
  if mc%2:print(sum(a)-min(a)*2)
  else:print(sum(a))

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = list(map(int, read().split()))

    neg = total = 0
    min_abs = INF
    for a in A:
        if a < 0:
            neg += 1
        total += abs(a)
        if min_abs > abs(a):
            min_abs = abs(a)

    if neg % 2 == 1:
        total -= 2 * min_abs

    print(total)
    return


def __starting_point():
    main()

__starting_point()

def main():
	N = int(input())
	A = [int(a) for a in input().split(" ")]
	if A.count(0) > 0:
		print((sum([abs(a) for a in A])))
		return 0
	minus = 0
	for i in range(len(A)):
		if A[i] < 0:
			minus += 1
	if minus % 2 == 0:
		print((sum([abs(a) for a in A])))
		return 0
	A.sort(key=lambda a: abs(a))
	print((sum([abs(a) for a in A[1:]]) - abs(A[0])))

main()


n = int(input())
a = list(map(int,input().split()))
m = 0
for i in range(n):
    if a[i] < 0:
        m += 1
        a[i] = abs(a[i])
if m % 2 == 0:
    print(sum(a))
else:
    print(sum(a) - (min(a) * 2))

N=int(input())
A=list(map(int,input().split()))

plus=0
zero=0
minus=0

for i in range(N):
    if A[i]>0:
        plus+=1
    elif A[i]<0:
        minus+=1
    else:
        zero+=1
ans=0
m=10**9+10
for i in range(N):
    ans+=abs(A[i])
    m=min(m,abs(A[i]))


if minus%2==0 or zero>0:
    pass
else:
    
    ans=ans-2*m

print(ans)

_,*A=map(int,open(0).read().split());print(sum(B:=[abs(a)for a in A])-2*min(B)*(sum(1 for a in A if a<0)%2))

N = int(input())
a_ls = list(map(int, input().split()))
abs_ls = [0] * N
minus = 0
for i in range(N):
    if a_ls[i] < 0:
        minus += 1
    abs_ls[i] = abs(a_ls[i])

if minus % 2 == 1:
    ans = sum(abs_ls) - 2 * min(abs_ls)
else:
    ans = sum(abs_ls)
print(ans)

N=int(input())
A=list(map(int,input().split()))
import bisect
A.sort()
B=[abs(i) for i in A]
l=min(B)
count=0
for i in range(N):
  if A[i]<0:
    count+=1
  else:
    break
if count%2==1:
  for i in range(count-1):
    A[i]=-A[i]

  print(sum(A)-2*l-2*A[count-1])

if count%2==0:
  for i in range(count):
    A[i]=-A[i]
  print(sum(A))

import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():






    n = I()
    a = LI()

    ans = 0
    mn = 0

    for i in range(n):
        if a[i] <0:
            mn += 1
            a[i] *= -1

    if (mn %2 == 0):
        ans = sum(a)
    else:
        ans = sum(a)-min(a)*2

    print(ans)

                    


main()


n = int(input())
a = list(map(int, input().split()))
b = []
cnt = 0
for i in range(n):
    b.append(abs(a[i]))
    if a[i] < 0:
        cnt += 1
if cnt % 2 == 0:
    print(sum(b))
else:
    print(sum(b)-min(b)*2)

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = list(map(int, read().split()))

    neg = sum(1 for a in A if a < 0)
    ans = sum(abs(a) for a in A)

    if neg % 2 == 1:
        ans -= 2 * min(abs(a) for a in A)

    print(ans)
    return


def __starting_point():
    main()

__starting_point()

N = int(input())
A = list(map(int,input().split()))

cnt = 0

for a in A:
  if a < 0:
    cnt += 1

A = list(map(lambda x: abs(x), A))
sum_A = sum(A)
    
if cnt % 2 == 0:
  print(sum_A)
  
else:
  A.sort()
  print(sum_A - 2 * min(A))

N = int(input())
As = list(map(int, input().split()))

#負の数カウントと絶対値リスト作成
abs_As = []
negative_count = 0

for A in As:
    if(A <= 0):
        abs_As.append(abs(A))
        negative_count += 1
    
    else:
        abs_As.append(A)

#print(As)
#print(abs_As)
#print(negative_count)

if(negative_count % 2 == 0):
    print(sum(abs_As))

else:
    print(sum(abs_As) - 2 * min(abs_As))

n = int(input())
a = list(map(int,input().split()))
c = 0
s = 0
ma = 10**6
for i in a:
    if i<0:
        c+=1
        c%=2
    s += abs(i)
    ma = min(ma,abs(i))
if c == 1:
    print((s-2*ma))
else:
    print(s)


def main():
    n=int(input())
    a=sorted(map(int,input().split()))
    aa=sorted(abs(i) for i in a)
    
    if sum(i<0 for i in a)%2==0:
        print(sum(aa))
    else:
        print(-aa[0]+sum(aa[1:]))

def __starting_point():
    main()
__starting_point()

def solve():
  N = int(input())
  A = list(map(int, input().split()))
  B = [abs(a) for a in A]
  ans = sum(B)
  under = [a for a in A if a<0]
  if len(under)%2==1:
    ans -= min(B)*2
  return ans
print(solve())

N = int(input())
A = list(map(int, input().split()))

m = 0

for i in range(N):
    if A[i] < 0:
        m += 1
        A[i] = -A[i]

if m % 2 == 0:
    print(sum(A))
else:
    print(sum(A) - 2 * min(A))

n = int(input())
a = list(map(int, input().split()))
b = min(a,key=abs)
c = 0
sum_abs_a = 0
for i in range(n):
  sum_abs_a += abs(a[i])
for i in a:
  if i < 0:
    c += 1
if c % 2 == 0:
  print(sum_abs_a)
else:
  print((sum_abs_a - abs(b)*2))




N = int(input())
A = list(map(int,input().split()))
cnt = 0
for i in range(N):
    if A[i] < 0:
        cnt += 1
        A[i] *= -1
A.sort()
if cnt % 2 == 1:
    print(sum(A[1:])-A[0])
else:
    print(sum(A))

n = int(input())
a = list(map(int, input().strip().split()))

num_odd_minus = 0
res = 0
min_num = abs(a[0])
for num in a:
    if num < 0:
        num_odd_minus += 1
    abs_num = abs(num)
    res += abs_num
    if min_num > abs_num:
        min_num = abs_num

if num_odd_minus % 2 == 1:
    res -= min_num * 2

print(res)


import numpy as np
N = int(input())
As = np.array(list(map(int, input().split())), dtype = "int64")
#%%
minus_num = len(np.where(As<0)[0])
abs_As = np.abs(As)

if 0 in As or minus_num%2 == 0:
    print(sum(abs_As))
else:
    print(sum(abs_As) - 2*min(abs_As))

# from pprint import pprint
# import math
# import collections
import numpy as np

n = int(input())
# n, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))

minus_signs = sum([1 for _ in a if np.sign(_) == -1])

if minus_signs % 2 == 0:
    res = sum([abs(_) for _ in a])
else:
    _min = min([abs(_) for _ in a])
    res = sum([abs(_) for _ in a])

    res = res - _min - _min

print(res)


#a, b, k = map(int, input().split( ))
n = int(input())
A = list(map(int,input().split()))

s = 0
m = 10**9
nimus = 0
for a in A:
  s += abs(a)
  m = min(m,abs(a))
  if a <0:
    nimus += 1

if nimus%2 == 0:
  print(s)
else:
  print((s-2*m))


n = int(input())
a = list(map(int,input().split()))

cnt_fu = 0
cnt_0 = 0
ans = 0
b = []
for i in range(n):
    ans += abs(a[i])
    b.append(abs(a[i]))
    if a[i]<0:
        cnt_fu += 1
    if a[i]==0:
        cnt_0 += 1
#print(cnt_fu,cnt_0,ans,b)
if cnt_fu%2==0:
    print(ans)
else:
    print((ans-min(b)*2))


N = int(input())
A = list(map(int, input().split()))

minus_cnt = 0
for a in A:
    if a < 0:
        minus_cnt += 1

abs_A = list(map(abs, A))
sum_ = sum(abs_A)

if minus_cnt % 2 == 0:
    ans = sum_
else:
    ans = sum_ - 2*min(abs_A)

print(ans)


n = int(input())
A = list(map(int,input().split()))

law_ans = 0
absminA = float('inf')
for a in A:
    law_ans += abs(a)
    absminA = min(absminA, abs(a))


cnt_neg = 0

for a in A:
    if a < 0:
        cnt_neg += 1

cnt_0 = A.count(0)

if cnt_neg%2 == 0:
    print(law_ans)
else:
    print((law_ans-2*absminA))



n = int(input())
a = list(map(int, input().split()))
mini = 10**9 + 1
s = 0
flag = 1
for i in a:
    mini = min(mini, abs(i))
    if i < 0:
        flag *= -1
    s += abs(i)
if flag == 1:
    print(s)
else :
    print(s-2*mini)

n = int(input())
lis = list(map(int, input().split()))

minus = 0
for i in range(n):
    if lis[i] < 0:
        minus += 1
        lis[i] = lis[i]*-1

if 0 in lis or minus % 2 == 0:
    print(sum(lis))
else:
    print(sum(lis) - 2*min(lis))

# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
import numpy as np
# import heapq
# from collections import deque

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

B = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

num_minus = len(B[B < 0])
abs_tot = sum(list(map(abs, A)))
if num_minus % 2 == 0:
    print(abs_tot)
else:
    n_0 = 10**9
    for i in A:
        a = abs(i)
        if a < n_0:
            n_0 = a
    print(abs_tot - (n_0 * 2))

N = int(input())
A = list(map(int, input().split()))
num_minus = sum([1 if v < 0 else 0 for v in A])
sum_abs = sum([abs(v) for v in A])
min_abs = min([abs(v) for v in A])
print(sum_abs if num_minus % 2 == 0 else sum_abs - min_abs * 2)

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def get_primenumber(number):#素数列挙
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list
def factrization_prime(number):#素因数分解
    factor = {}
    div = 2
    s = math.sqrt(number)
    while div < s:
        div_cnt = 0
        while number % div == 0:
            div_cnt += 1
            number //= div
        if div_cnt != 0:
            factor[div] = div_cnt
        div += 1
    if number > 1:
        factor[number] = 1
    return factor
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
num = []
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

n = k()
A = l()

for i in A:
    if i<=0:
        cnt += 1

if cnt % 2 == 0:
    A = list(map(lambda k:abs(k), A))
    print(sum(A))
else:
    A = list(map(lambda k:abs(k), A))
    a = min(A)
    print(sum(A)-2*a)

def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [None] * n
    cnt = 0
    for i in range(n):
        if A[i] <= 0:
            cnt += 1
        B[i] = abs(A[i])
    print((sum(B) - 2 * min(B) if cnt % 2 == 1 else sum(B)))


def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(map(int, input().split()))

a.sort()
abs_a = [abs(x) for x in a]
minus = []

for x in a:
    if x < 0:
        minus.append(x)

tmp = sum(abs_a)

if len(minus) % 2 == 0:
    print(tmp)
else:
    print(tmp - min(abs_a)*2)

n = int(input())
lis = list(map(int, input().split()))

if 0 in lis:
    ans = 0
    for i in lis:
        if i < 0:
            ans += -1 * i
        else:
            ans += i
    print(ans)
    return

minus = [0]*n
for i in range(n):
    if lis[i] < 0:
        minus[i] = 1

if sum(minus) % 2 == 0:
    ans = 0
    for i in lis:
        if i < 0:
            ans += -1 * i
        else:
            ans += i
    print(ans)
else:
    ans = 0
    m = 10**9+1
    for i in lis:
        if i < 0:
            ans += -1*i
        else:
            ans += i
        m = min(m, abs(i))
    print((ans - 2*m))


n=int(input())
a=list(map(int,input().split()))

minus_num = 0
for i in range(n):
  if a[i] < 0:
    minus_num += 1

abs_a = list(map(abs,a))
if minus_num % 2 == 0:
  print(sum(abs_a))
else:
  print(sum(abs_a)-2*min(abs_a))

N = int(input())
lsA = map(int,input().split())
mainasu = 0
minabs = 10**10
ls2 = []
for i in lsA:
    if i < 0:
        mainasu += 1
        ls2.append(-i)
    else:
        ls2.append(i)
    minabs = min(minabs,abs(i))
if mainasu%2 == 0:
    print(sum(ls2))
else:
    print(sum(ls2)-2*minabs)

N = int(input())
A = [int(_) for _ in input().split()]

cnt = 0
for i in range(N):
    if A[i] < 0:
        cnt += 1
        A[i] *= -1

if cnt % 2 == 0:
    print((sum(A)))
else:
    print((sum(A) - min(A) * 2))


N = int(input())
A = list(map(int, input().split()))
tmp = 10**10
minus = 0
zeros = 0
ans = 0
for a in A:
  if a > 0:
    ans += a
    tmp = min(tmp, a)
  elif a == 0:
    zeros += 1
  else:
    a = -a
    ans += a
    minus += 1
    tmp = min(tmp, a)
if minus % 2 == 1 and zeros == 0:
  ans -= tmp*2
print(ans)

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()
    A_abs = [abs(i) for i in A]

    if len([i for i in A if i < 0]) % 2 == 1:
        ans = sum(A_abs) - 2 * min(A_abs)
    else:
        ans = sum(A_abs)

    print(ans)

def __starting_point():
    resolve()

__starting_point()

N = int(input())
A = list(map(int,input().split()))

minus_cnt = 0
abs_sum = 0
min_abs_val = 1000000000
for i in range(N):
    val = A[i]
    abs_val = abs(val)
    abs_sum += abs_val
    if abs_val < min_abs_val:
        min_abs_val = abs_val
    if val < 0:
        minus_cnt += 1

B_max_sum = abs_sum
if (minus_cnt % 2 != 0) and (min_abs_val != 0):
    B_max_sum -= (min_abs_val * 2)

print(B_max_sum)



import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N = NI()
    A = NLI()
    
    cnt = 0
    minimum_abs = 10**9
    ans = 0
    flag = 0
    
    for n in range(N):
        ans += abs(A[n])
        minimum_abs = min(abs(A[n]),minimum_abs)
        if A[n] < 0:
            cnt += 1
        elif A[n] == 0:
          flag = 1

                
    if cnt % 2 == 0 or flag == 1:
        print(ans)
    else:
        print(ans - minimum_abs * 2)
            


def __starting_point():
    main()
__starting_point()

n=int(input())
A=list(map(int,input().split()))
cnt = sum([0 if a>0 else 1 for a in A])
absA = sorted([abs(a) for a in A])
if cnt % 2 == 1:
  print(sum(absA)-2*absA[0])
else:
  print(sum(absA))

import numpy
N = int(input())
a = numpy.array([int(i) for i in input().split()])
min =  10**9+1
minus = 0
total = 0
for i in a :
    if i < 0 :
        minus += 1
    if abs(i) < min :
        min = abs(i)
    total += abs(i)
#    print(i,min,total)
if minus %2 == 0 :
    print(total)
else :
    print((total-min*2))


N = int(input())
A = list(map(int,input().split()))

minus_cnt = 0
abs_sum = 0
min_abs_val = 1000000000
for i in range(N):
    val = A[i]
    abs_val = abs(val)
    abs_sum += abs_val
    if abs_val < min_abs_val:
        min_abs_val = abs_val
    if val < 0:
        minus_cnt += 1

B_max_sum = abs_sum
if minus_cnt % 2 != 0:
    B_max_sum -= (min_abs_val * 2)

print(B_max_sum)



n = int(input())
a = list(map(int,input().split()))
ans = 0
cnt_minus = 0
cnt_zero = 0
m = 10**9
for i in a:
    ans += abs(i)
    if i<0:
        cnt_minus += 1
    if i==0:
        cnt_zero +=1
    m = min(m,abs(i))

if cnt_minus % 2 == 0 or cnt_zero !=0:
    print(ans)
else:
    print((ans-2*m))



n = int(input())
aa = list(map(int, input().split()))
bb = [abs(a) for a in aa]

if sum(x<0 for x in aa) % 2 == 0:
  print(sum(bb))
else:
  
  print(sum(bb)-2*min(bb))

N = int(input())
A = list(map(int,input().split()))
B = list(map(abs,A))
print(sum(B)-2*min(B)*(sum(a<0 for a in A)%2))

N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(N):
    if A[i] < 0:
        cnt += 1
A = [abs(a) for a in A]
if cnt % 2 == 0:
    print(sum(A))
else:
    print(sum(A)-2*min(A))

n = int(input())
A = list(map(int,input().split()))

cnt = 0
A_ = []
for i in A:
    if i < 0:
        cnt += 1
        A_.append(-i)
    else:
        A_.append(i)

if cnt%2 == 0:
    print((sum(A_)))
else:
    print((sum(A_) - 2*min(A_)))


n = int(input())
A = list(map(int, input().split()))
cnt = 0
s = 0
m = 10 ** 9
for ai in A:
    if ai <= 0:
        cnt = cnt + 1
        ai *= (-1)
    s += ai
    if m > ai:
        m = ai
if cnt % 2 == 0:
    for a in A:
        ans = s
else:
    ans = s - 2*m
print(ans)

n = int(input())
A = list(map(int,input().split()))
B = [abs(a) for a in A]
ans=sum(B)
c=sum(1 for a in A if a<0)
if c%2 :
    ans-=min(B)*2
print(ans)


n = int(input())
list_A = list(map(int, input().split()))
m = pow(10, 10)
s = 0
cnt = 1

for a in list_A:
    m = min(m, abs(a))
    if a < 0:
        cnt *= -1
    s += abs(a)

if cnt == 1:
    print(s)
else:
    print(s - 2 * m)

N=int(input())
A=list(map(int,input().split()))
zero=False
minus=0
for i in range(N):
    if A[i]<0:
        A[i]*=-1
        minus=1-minus
    elif A[i]==0:
        zero=True

A.sort(reverse=True)
if zero==True:
    print((sum(A)))
else:
    if minus==0:
        print((sum(A)))
    else:
        print((sum(A[0:N-1])-A[-1]))


n = int(input())
a = list(map(int, input().split()))

a.sort()
minus, plus = [], []

for x in a:
    if x < 0:
        minus.append(x)
    else:
        plus.append(x)

tmp = sum([abs(x) for x in a])

if len(minus) % 2 == 0:
    print(tmp)
else:
    if plus == [] or abs(minus[-1]) < plus[0]:
        print(tmp + minus[-1] * 2)
    else:
        print(tmp - plus[0] * 2)

from bisect import bisect_left,bisect,bisect_right
import sys

icase=0
if icase==0:
    n=int(input())
    a=list(map(int,input().split()))

a.sort()
ii=bisect(a,0)

if ii==n:
    if ii%2==0:
        asum=-sum(a)
    else:    
        asum=-sum(a[0:ii-1])+a[ii-1]
    print(asum)
    return

if ii%2==0:
    asum=-sum(a[0:ii])+sum(a[ii:])
else:
    if -a[ii-1]<a[ii]:
        d=a[ii-1]+a[ii]
    else:
        d=-a[ii-1]-a[ii]
    asum=-sum(a[0:ii-1])+d+sum(a[ii+1:])

print(asum)


n = int(input())
A = list(map(int, input().split()))

# マイナスの数が偶数ならば、絶対値を取って和を出力する。
# マイナスの数が奇数ならば、絶対値を取った和から絶対値が一番小さいもの*2を引く。
abs_min = 10**9
flag = False
if A.count(0) >= 1:
  flag = True
neg_count = 0
ans = 0
for a in A:
  ans += abs(a)
  if a < 0:
    neg_count += 1
  if abs(a) < abs_min:
      abs_min = abs(a)
if neg_count %2 == 0:
  flag = True

if flag:
  print(ans)
else:
  print(ans - 2 * abs_min)

n = int(input())
A = list(map(int,input().split()))

law_ans = 0
absminA = float('inf')
for a in A:
    law_ans += abs(a)
    absminA = min(absminA, abs(a))


cnt_neg = 0

for a in A:
    if a < 0:
        cnt_neg += 1

cnt_0 = A.count(0)

if cnt_neg%2 == 0:
    print(law_ans)
else:
#０があるときはいつでもlaw_ansになるが、absminAが0だからおっけい
    print((law_ans-2*absminA))
    



N = int(input())
a_ls = list(map(int, input().split()))

dp = [[0,0] for _ in range(N)]
dp[1][0] = a_ls[1] + a_ls[0]
dp[1][1] = -dp[1][0]

for i in range(2,N):
    # flipなしでa_ls[i]を追加
    dp[i][0] = max(dp[i-1][0] + a_ls[i], dp[i-1][1] + a_ls[i])

    # flipありでa_ls[i]を追加
    dp[i][1] = max(dp[i-1][0] - 2*a_ls[i-1] - a_ls[i],dp[i-1][1] + 2*a_ls[i-1] - a_ls[i])

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


def main():
    n = int(input())
    a = list(map(int, input().split()))
    s, cnt = [0]*n, 0
    for i in range(n):
        s[i] = abs(a[i])
        if a[i] < 0:
            cnt += 1
    if cnt%2:
        print(sum(s) - 2*min(s))
    else:
        print(sum(s))

def __starting_point():
    main()
__starting_point()

n=int(input())
A=list(map(int,input().split()))
cnt = sum([0 if a>0 else 1 for a in A])
absA = sorted([abs(a) for a in A])
if cnt % 2 == 1:
  print(sum(absA)-2*absA[0])
else:
  print(sum(absA))

n=int(input())
a=list(map(int,input().split()))
dp=[[0,0]for _ in range(n)]
dp[0]=[a[0],-a[0]]
for i in range(1,n):
  dp[i][0]=max(dp[i-1][0]+a[i],dp[i-1][1]-a[i])
  dp[i][1]=max(dp[i-1][0]-a[i],dp[i-1][1]+a[i])
print(dp[n-1][0])