AtCoder Beginner Contest 125 - Flipping Signs

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

Starter code:

Solutions:
N = int(input())
A = list(map(int, input().split()))
S = [-A[i] for i in range(N) if A[i] <= 0]
T = list(map(abs, A))
ans = sum(T)
if len(S) % 2 != 0:
	ans -= min(T) * 2
print(ans)


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


n = int(input())
a = list(map(int, input().split()))
k = 0
for t in a:
	if t < 0:
		k += 1
k = k % 2
b = [abs(t) for t in a]
b.sort(reverse=1)
print(sum(b) - 2 * k * b[-1])


n = int(input())
a = []
mc = 0
for x in input().split():
	i = int(x)
	if i < 0:
		mc += 1
		i = -i
	a.append(i)
s = sum(a)
print(s if mc % 2 == 0 else s - 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):
	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()))
t = 0
for i in range(n):
	if a[i] < 1:
		t += 1
	a[i] = abs(a[i])
a.sort()
print(sum(a) if t % 2 == 0 else sum(a) - 2 * a[0])


N = int(input())
A = list(map(int, input().split()))
cnt = sum([1 for i in A if i < 0])
A = list(map(abs, A))
ret = sum(A) - min(A) * (1 - (-1) ** cnt)
print(ret)


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


n = int(input())
a = [int(S) for S in input().split()]
c = 0
for x in range(n):
	if a[x] < 0:
		a[x] *= -1
		c += 1
ans = sum(a)
if c % 2 == 1:
	ans -= 2 * min(a)
print(ans)


n = int(input())
A = list(map(int, input().split()))
count = 0
S = []
for a in A:
	S.append(abs(a))
	if a < 0:
		count += 1
S.sort()
print(sum(S) if count % 2 == 0 else sum(S[1:]) - S[0])


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


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 = input()
a = list(map(int, input().split()))
n = sum((x < 0 for x in a))
a = list(map(lambda x: abs(x), a))
m = min(a)
s = sum(a) if n % 2 == 0 else sum(a) - m * 2
print(s)


(_, a) = open(0)
(*a,) = map(int, a.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 = [*map(int, input().split())]
c = 0
l = []
for i in a:
	if i < 0:
		c += 1
	l += [abs(i)]
print(sum(l) - [0, min(l) * 2][c % 2])


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


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


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


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()))
ans = sum((abs(ai) for ai in a))
if sum((ai < 0 for ai in a)) % 2:
	ans -= 2 * min((abs(ai) for ai in a))
print(ans)


(_, *a) = map(int, open(0).read().split())
(*z,) = map(abs, a)
s = sum(z)
print(s if len([i for i in a if i < 0]) % 2 == 0 or 0 in a else s - min(z) * 2)


N = int(input())
a = list(map(int, input().split()))
sign = len([i for i in a if i < 0]) % 2
b = list(map(abs, a))
b.sort()
if sign == 0:
	print(sum(b))
else:
	print(sum(b) - b[0] * 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()))
cnt = sum((1 for a in A if a < 0))
ls = list(map(abs, A))
ans = sum(ls)
if cnt % 2 == 0:
	print(ans)
else:
	print(ans - 2 * min(ls))


(N, *A) = map(int, open(0).read().split())
p = 0
q = -10 ** 18
for a in A:
	(p, q) = (max(p + a, q - a), max(p - a, q + a))
print(p)


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_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):
	dp[i][0] = max(dp[i - 1][0] + a_ls[i], dp[i - 1][1] + 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(max(dp[-1][0], dp[-1][1]))


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


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


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, *A) = map(int, open(0).read().split())
ans = sum(map(abs, A))
if len([a for a in A if a < 0]) % 2 == 1:
	ans -= 2 * min(map(abs, A))
print(ans)


(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,) = map(int, input().split())
aA = [abs(a) for a in A]
asum = sum(aA)
c = sum([a < 0 for a in A])
if c % 2:
	print(asum - min(aA) * 2)
else:
	print(asum)


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


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


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


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 = list(map(int, input().split()))
neg = 0
for i in range(N):
	if A[i] < 0:
		A[i] = -A[i]
		neg += 1
if neg % 2 == 0:
	print(sum(A))
else:
	print(sum(A) - 2 * min(A))


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()))
cnt = 0
for i in range(n):
	if a[i] < 0:
		cnt += 1
		a[i] *= -1
a.sort()
cnt %= 2
print(sum(a) - 2 * sum(a[:cnt]))


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()))
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))
elif minus == 0:
	print(sum(A))
else:
	print(sum(A[0:N - 1]) - A[-1])


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


(_, *aa) = map(int, open(0).read().split())
bb = tuple(map(abs, aa))
m = tuple((a for a in aa if a < 0))
print(sum(bb) - min(bb) * 2 * (len(m) % 2))


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


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


(_, *a) = map(int, open(0).read().split())
l = [*map(abs, a)]
print(sum(l) - sum((i < 0 for i in a)) % 2 * min(l) * 2)


num = int(input())
a = list(map(int, input().split(' ')))
fu = 1
for i in range(num):
	if a[i] < 0:
		fu *= -1
		a[i] *= -1
print(sum(a) if fu == 1 else sum(a) - min(a) * 2)


(_, *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 = [int(i) for i in input().split()]
(x, m, num) = (10 ** 9, 0, 0)
for i in a:
	if i < 0:
		m += 1
	x = min(abs(i), x)
	num += abs(i)
if x and m % 2:
	print(num - 2 * x)
else:
	print(num)


N = int(input())
A = list(map(int, input().split()))
B = [abs(a) for a in A]
M = len([a for a in A if a < 0])
if M % 2 == 0:
	print(sum(B))
else:
	print(sum(B) - 2 * min(B))


n = input()
l = list(map(int, input().split()))
cnt = len([i for i in l if i < 0])
abs_l = list(map(abs, l))
print(sum(abs_l) if cnt % 2 == 0 else sum(abs_l) - 2 * min(abs_l))


N = int(input())
A = list(map(int, input().split()))
K = len([a for a in A if a < 0])
B = sorted([abs(a) for a in A])
if K % 2 == 0:
	print(sum(B))
else:
	print(sum(B[1:]) - B[0])


n = int(input())
a = [int(i) for i in input().split()]
x = 0
b = []
for i in a:
	if i < 0:
		x = x + 1
	b.append(abs(i))
b.sort()
print(sum(b) - b[0] * 2 if x % 2 else sum(b))


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


N = int(input())
A = list(map(int, input().split()))
B = sorted(map(abs, A))
if sum((x < 0 for x in A)) % 2 == 0:
	print(sum(B))
else:
	print(sum(B[1:]) - B[0])


(N, *A) = map(int, open(0).read().split())
(x, y) = (0, -10000000000.0)
for a in A:
	(x, y) = (max(x + a, y - a), max(x - a, y + a))
print(x)


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


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


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


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


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,) = map(int, input().split())
if sum((a < 0 for a in A)) & 1:
	print(sum(map(abs, A)) - 2 * min((abs(a) for a in A)))
else:
	print(sum(map(abs, A)))


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


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


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(abs, aaa))
print(sum(bbb) - 2 * min(bbb) * (sum((1 for a in aaa if a < 0)) % 2))


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


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


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


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


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


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


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


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()))
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()))
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())
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())
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())
a = list(map(int, input().split()))
b = list(filter(lambda x: x < 0, a))
n = len(b)
c = list(map(abs, a))
d = c
s = sum(c)
if n & 1 == 1:
	s -= min(d) * 2
print(s)


N = int(input())
A = [int(a) for a in input().split()]
minusnum = sum((a < 0 for a in A))
ablist = [abs(a) for a in A]
ans = sum(ablist)
if minusnum % 2:
	ans = ans - 2 * min(ablist)
print(ans)


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()))
cm = len([ai for ai in a if ai < 0])
a = [abs(ai) for ai in a]
if cm % 2 == 0:
	print(sum(a))
else:
	print(sum(a) - 2 * min(a))


N = int(input())
t = list(map(int, input().split()))
mins = [x for x in t if x < 0]
if len(mins) % 2 == 0:
	print(sum(map(abs, t)))
else:
	print(sum(map(abs, t)) - 2 * min(map(abs, t)))


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())
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)
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()))
sign = [1 if i < 0 else 0 for i in a]
a_abs = [abs(i) for i in a]
if sum(sign) % 2 == 0:
	print(sum(a_abs))
else:
	print(sum(a_abs) - 2 * min(a_abs))


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


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


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


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)


MAX_N = 1000000000
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()))
count = 0
for a in A:
	count += a < 0
a = sorted(map(abs, A))
if not count % 2:
	print(sum(a))
else:
	print(sum(a[1:]) - a[0])


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


n = int(input())
a = sorted(map(int, input().split()))
print(sum(map(lambda a, b: abs(a + b), a[::2], a[1::2])) + (a[-1] if n % 2 == 1 else 0))


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 = input()
AA = input()
A = list(map(int, AA.replace('-', '').split()))
HC = AA.count('-')
if HC % 2 == 0:
	print(sum(A))
else:
	print(sum(A) - sorted(A)[0] * 2)


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)


n = int(input())
A = list(map(int, input().split()))
dp = [[0] * 2 for _ in range(n)]
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 = int(input())
A = list(map(int, input().split()))
c = 0
s = 0
Az = []
for i in A:
	if i < 0:
		c += 1
	s += abs(i)
	Az.append(abs(i))
if c % 2 == 0:
	print(s)
else:
	print(s - 2 * min(Az))


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


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


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()))
neg_parity = sum((a < 0 for a in A)) % 2
A = sorted((a if a >= 0 else -a for a in A))
print(sum(A) - neg_parity * 2 * A[0])


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
if cnt_fu % 2 == 0:
	print(ans)
else:
	print(ans - min(b) * 2)


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


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


N = int(input())
A = [int(i) for i in input().split()]
(a, b) = (0, -10000000000.0)
for ai in A:
	(a, b) = (max(a + ai, b - ai), max(a - ai, b + ai))
print(a)


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)
elif plus == [] or abs(minus[-1]) < plus[0]:
	print(tmp + minus[-1] * 2)
else:
	print(tmp - plus[0] * 2)


n = int(input())
(*a,) = map(int, input().split())
(*_a,) = map(abs, a)
if sum(map(lambda x: x < 0, a)) % 2 == 0:
	print(sum(_a))
else:
	mi = min(_a)
	print(sum(_a) - 2 * mi)


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


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()))
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, *a) = map(int, open(0).read().split())
b = sum([i < 0 for i in a]) % 2
a = [abs(i) for i in a]
print(sum(a) if b == 0 or 0 in a else sum(a) - min(a) * 2)


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


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


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())
l = [*map(int, input().split())]
c = 0
for (e, i) in enumerate(l):
	if i < 0:
		c += 1
		l[e] = -i
print(sum(l) - [0, min(l) * 2][c % 2])


N = int(input())
A = [int(x) for x in input().split()]
B = [x for x in A if x < 0]
absA = [abs(x) for x in A]
if len(B) % 2 == 0:
	minus = 0
else:
	minus = min(absA)
print(sum(absA) - minus * 2)


n = int(input())
a = list(map(int, input().split()))
mn = 10 ** 18
ng = 0
sm = 0
for i in a:
	sm += abs(i)
	mn = min(mn, abs(i))
	if i < 0:
		ng += 1
if ng % 2 == 0:
	print(sm)
else:
	print(sm - mn * 2)


n = int(input())
A = list(map(int, input().split()))
neg_A = len(list(filter(lambda x: x < 0, A)))
A = sorted(map(abs, A))
if neg_A % 2 == 0:
	print(sum(A))
else:
	print(sum(A) - 2 * A[0])


n = int(input())
a = list(map(int, input().split()))
su = sum(map(abs, a))
li = [i for i in a if i < 0]
if len(li) % 2 != 0 and 0 not in a:
	su -= 2 * min(map(abs, a))
print(su)


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


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)


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


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


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


N = int(input())
X = list(map(int, input().split()))
y = [abs(v) for v in X]
if sum((v < 0 for v in X)) % 2 == 0:
	print(sum(y))
else:
	print(sum(y) - 2 * min(y))


N = int(input())
An = list(map(int, input().split()))
M = sum([0 if a >= 0 else 1 for a in An])
An = [abs(a) for a in An]
if M % 2 == 0:
	print(sum(An))
else:
	print(sum(An) - 2 * min(An))


N = int(input())
L = list(map(int, input().split()))
count = 0
sum = 0
A = float('inf')
for i in L:
	sum += abs(i)
	A = min(A, abs(i))
	if i < 0:
		count += 1
if count % 2 == 0:
	print(sum)
else:
	print(sum - A * 2)


(N, *A) = map(int, open(0).read().split())
B = [abs(i) for i in A]
print(sum(B) - 2 * min(B) if len([i for i in A if i < 0]) % 2 else sum(B))


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


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()))
absA = list(map(abs, A))
sumA = sum(absA)
if sum((i < 0 for i in A)) % 2 == 1:
	print(sumA - 2 * min(absA))
else:
	print(sumA)


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 math
n = int(input())
M = list(map(int, input().split()))
p = [q < 0 for q in M].count(True)
X = [abs(x) for x in M]
if p % 2 == 0:
	print(sum(X))
else:
	print(sum(X) - min(X) * 2)


n = int(input())
a = sorted(list(map(int, input().split())))
for i in range(n - 1):
	if a[i] + a[i + 1] < 0:
		a[i] = -a[i]
		a[i + 1] = -a[i + 1]
print(sum(a))


n = int(input())
A = [int(a) for a in input().split()]
B = [1 if _ > 0 else 0 for _ in A]
D = [abs(d) for d in A]
i = B.count(0)
if i % 2 != 0:
	D[D.index(min(D))] *= -1
print(sum(D))


N = int(input())
A = [int(i) for i in input().split()]
B = [abs(i) for i in A]
minus = 0
for i in A:
	if i < 0:
		minus += 1
if minus % 2 == 0:
	print(sum(B))
else:
	print(sum(B) - 2 * min(B))


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)
if minus % 2 == 0:
	print(total)
else:
	print(total - min * 2)


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


import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = np.array(A)
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()))
A_ = sorted([i if i > 0 else -i for i in A])
print(sum(A_) - A_[0] * 2 * ((N - len([i for i in A if i > 0])) % 2))


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


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


n = int(input())
a = list(map(int, input().split()))
neg = 0
for i in a:
	if i < 0:
		neg += 1
a = sorted(list(map(abs, a)))
ans = sum(a)
if neg % 2 == 1:
	ans -= 2 * a[0]
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))


_ = input()
(*A,) = map(int, input().split())
N = [a for a in A if a < 1]
A = list(map(abs, A))
print(sum(A) - 2 * min(A) * (len(N) % 2))


x = int(input())
y = list(map(int, input().split()))
t = 1
for i in range(x):
	if y[i] < 0:
		t = t * -1
	y[i] = abs(y[i])
if t == 1:
	print(sum(y))
else:
	print(sum(y) - min(y) * 2)


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


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


N = int(input())
A = list(map(int, input().split()))
NS = sum((int(a < 0) for a in A))
S = sum((abs(a) for a in A))
m = min((abs(a) for a in A))
print(S - 2 * m if NS & 1 else S)


n = int(input())
(*l,) = map(int, input().split())
minus = 0
for i in range(n):
	if l[i] < 0:
		minus += 1
		l[i] *= -1
ans = sum(l)
if minus % 2 == 1:
	ans -= 2 * min(l)
print(ans)


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)


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


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 = len([x for x in a if x < 0])
a = list(map(abs, a))
a.sort()
print(sum(a) if m % 2 == 0 else sum(a[1:]) - a[0])


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)


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)


input()
A = list(map(int, input().split()))
cnt = len([i for i in A if i < 0])
abs_A = [abs(i) for i in A]
if not cnt % 2:
	print(sum(abs_A))
else:
	print(sum(abs_A) - 2 * min(abs_A))


n = int(input())
a = list(map(int, input().split(' ')))
b = list(filter(lambda x: x < 0, a))
a = list(map(abs, a))
if len(b) % 2 == 0:
	print(sum(a))
else:
	print(sum(a) - min(a) * 2)


N = int(input())
A = list(map(int, input().split()))
ans = 0
mins = 10 ** 10
ct = 0
for i in A:
	ans += abs(i)
	mins = min(mins, abs(i))
	if i < 0:
		ct += 1
if ct % 2 == 1:
	ans -= 2 * mins
print(ans)


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


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


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


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))
	while search_list[0] <= math.sqrt(number):
		head_num = search_list.pop(0)
		prime_list.append(head_num)
		search_list = [num for num in search_list if num % head_num != 0]
	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)


I = lambda : list(map(int, input().split()))
N = int(input())
A = I()
B = [abs(a) for a in A]
m = sum((1 * (a < 0) for a in A)) % 2
if m == 0:
	print(sum(B))
else:
	print(sum(B) - min(B) * 2)


n = int(input())
a = list(map(int, input().split()))
s = sum(map(abs, a))
c = min(list(map(abs, a)))
z = []
for i in a:
	if i < 0:
		z.append(i)
x = len(z) % 2
if x:
	print(s - 2 * c)
else:
	print(s)


N = int(input())
A = list(map(int, input().split()))
souwa = 0
cnt = 0
keep = 10000000000.0
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))


n = int(input())
li = list(map(int, input().split()))
mainus_li = [i for i in li if i < 0]
li = [abs(i) for i in li]
ans = sum(li)
if len(mainus_li) % 2 == 1:
	ans -= 2 * min(li)
print(ans)


import sys

def solve(N: int, A: 'List[int]'):
	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])

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	A = [int(next(tokens)) for _ in range(N)]
	print(solve(N, A))

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

def __starting_point():
	main()
__starting_point()


N = int(input())
A = [int(x) for x in input().split()]
ABS = sorted([abs(a) for a in A])
minus = sum([1 for a in A if a < 0])
if minus % 2:
	ABS[0] *= -1
print(sum(ABS))


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


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()))
ab = list(map(abs, a[:]))
s = sum(ab[:])
m = len([i for i in a if i < 0])
if m % 2 == 0:
	print(s)
else:
	print(s - 2 * min(ab))


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()))
a_abs = [abs(x) for x in a]
cnt = [1 for x in a if x < 0]
if cnt.count(1) % 2 > 0:
	print(sum(a_abs) - 2 * min(a_abs))
else:
	print(sum(a_abs))


(N, *A) = map(int, open(0).read().split())
s = list((abs(x) for x in A))
cnt = sum((x < 0 for x in A))
if cnt % 2 == 0 or 0 in A:
	print(sum(s))
else:
	print(sum(s) - 2 * min(s))


import numpy as np
n = int(input())
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)


N = int(input())
INF = float('inf')
A = list(map(int, input().split()))
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])
ans = max(dp[N - 1])
print(ans)


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


n = int(input())
a = list(map(int, input().split()))
a_abs = list(map(abs, a))
q = 0
fu = [i for i in a if i < 0]
if len(fu) % 2 == 1:
	q = 2 * min(a_abs)
print(sum(a_abs) - q)


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)


N = int(input())
A = list(map(int, input().split()))
S = sum(map(abs, A))
sign = 1
for i in range(N):
	if A[i] < 0:
		sign *= -1
print(S if sign > 0 or 0 in A else S - 2 * min(map(abs, A)))