Yaroslav has an array, consisting of (2·n - 1) integers. In a single operation Yaroslav can change the sign of exactly n elements in the array. In other words, in one operation Yaroslav can select exactly n array elements, and multiply each of them by -1.

Yaroslav is now wondering: what maximum sum of array elements can be obtained if it is allowed to perform any number of described operations?

Help Yaroslav.


-----Input-----

The first line contains an integer n (2 ≤ n ≤ 100). The second line contains (2·n - 1) integers — the array elements. The array elements do not exceed 1000 in their absolute value.


-----Output-----

In a single line print the answer to the problem — the maximum sum that Yaroslav can get.


-----Examples-----
Input
2
50 50 50

Output
150

Input
2
-1 -100 -1

Output
100



-----Note-----

In the first sample you do not need to change anything. The sum of elements equals 150.

In the second sample you need to change the sign of the first two elements. Then we get the sum of the elements equal to 100.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
n = int(input())
lst = [int(x) for x in input().split()]
x = len([elem for elem in lst if elem < 0])
values = sorted([abs(elem) for elem in lst])
result = sum(values)
if n % 2 == 0 and x % 2 == 1:
	result -= 2 * values[0]
print(result)


if True:
	n = int(input())
	a = [int(x) for x in input().split()]
	c = 0
	s = 0
	x = []
	for i in range(2 * n - 1):
		if a[i] < 0:
			c += 1
		s += abs(a[i])
		x.append(abs(a[i]))
	if n % 2:
		print(s)
	elif c % n == 0:
		print(s)
	elif c % 2 == 0:
		print(s)
	else:
		print(s - 2 * min(x))


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


n = int(input())
a = list(map(int, input().split()))
abs_a = [abs(v) for v in a]
neg = sum((v < 0 for v in a))
if n % 2 == 1 or neg % 2 == 0 or any((v == 0 for v in a)):
	print(sum(abs_a))
else:
	print(sum(abs_a) - 2 * min(abs_a))


def main():
	n = int(input())
	seq = list(map(int, input().split()))
	neg = [x for x in seq if x < 0]
	seq = [abs(x) for x in seq]
	ans = sum(seq)
	if n % 2 == 0 and len(neg) % 2 == 1:
		ans = ans - 2 * sorted(seq)[0]
	print(ans)
main()


(n, t) = (int(input()), list(map(int, input().split())))
p = list(map(abs, t))
s = sum(p)
if n & 1 == 0 and len([0 for i in t if i < 0]) & 1:
	s -= 2 * min(p)
print(s)


n = int(input())
a = list(map(int, input().split()))
c = 0
for cc in a:
	if cc < 0:
		c += 1
if 0 in a:
	print(sum((abs(x) for x in a)))
elif n % 2 == 0 and c % 2 == 1:
	print(sum((abs(x) for x in a)) - 2 * min(map(abs, a)))
else:
	print(sum((abs(x) for x in a)))


3
n = int(input())
data = list(map(int, input().split()))
(negative, zero, positive) = (0, 0, 0)
for x in data:
	if x < 0:
		negative += 1
	elif x == 0:
		zero += 1
	else:
		positive += 1
seen = {}
min_negative = negative

def go(negative, positive):
	nonlocal n, min_negative
	if (negative, positive) in seen:
		return
	seen[negative, positive] = True
	min_negative = min(min_negative, negative)
	for i in range(min(n, negative) + 1):
		for j in range(min(n - i, zero) + 1):
			k = n - i - j
			if k <= positive:
				go(negative - i + k, positive - k + i)
go(negative, positive)
values = sorted(list(map(abs, data)))
for i in range(min_negative):
	values[i] *= -1
print(sum(values))


def numneg(arr):
	s = 0
	for x in arr:
		if x < 0:
			s += 1
	return s

def negmax(arr):
	maxi = float('inf')
	for x in arr:
		if abs(x) < maxi:
			maxi = abs(x)
	return -maxi

def sumabs(arr):
	s = 0
	for x in arr:
		s += abs(x)
	return s
n = int(input())
a = list(map(int, input().split()))
if numneg(a) % 2 == 0 or n % 2 == 1:
	print(sumabs(a))
else:
	print(sumabs(a) + negmax(a) * 2)


n = int(input())
data = list(map(int, input().split()))
x = 0
for element in data:
	if element < 0:
		x += 1
values = sorted(list(map(abs, data)))
result = sum(values)
if n % 2 == 0 and x % 2 == 1:
	result -= 2 * values[0]
print(result)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = list(map(int, input().split()))
	(su, b, mi) = (0, 0, 10000)
	for i in a:
		su += abs(i)
		b += i < 0
		mi = min(mi, abs(i))
	if b >= n:
		b -= n
	print(su - 2 * mi * (not (not b % 2 or n % 2)))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
p = [int(x) for x in input().split()]
s = 0
for i in p:
	if i <= 0:
		s += 1
if n % 2 == 0 and s % 2 != 0:
	q = 1000
	for i in p:
		if abs(i) <= q:
			q = abs(i)
	print(sum((abs(i) for i in p)) - 2 * q)
else:
	print(sum((abs(i) for i in p)))


n = int(input())
arr = [int(x) for x in input().split()]
neg = []
pos = []
ans = sum(arr)
for i in range(2 * n - 1):
	if arr[i] < 0:
		neg.append(arr[i])
	pos.append(abs(arr[i]))
if len(neg) & 1 and n + 1 & 1:
	print(sum(pos) - 2 * min(pos))
else:
	print(sum(pos))


n = int(input())
a = list(map(int, input().split()))
c = list(map(abs, a))
if len(list(filter(lambda x: x < 0, a))) & 1 and n + 1 & 1:
	print(sum(c) - 2 * min(c))
else:
	print(sum(c))


def main():
	n = int(input())
	l = list(map(int, input().split()))
	res = sum(map(abs, l))
	if not n & 1 and sum((x < 0 for x in l)) & 1:
		res -= abs(min(l, key=abs)) * 2
	print(res)
main()


n = int(input())
a = sorted(map(int, input().split()))
b = map(lambda x: abs(x), a)
ans = sum(a)
for i in range(1, n + n - 1, 2):
	a[i] *= -1
	a[i - 1] *= -1
	ans = max(ans, sum(a))
if n % 2 == 1:
	ans = max(ans, sum(b))
print(ans)


n = int(input())
a = list(map(int, input().split()))
x = list(map(abs, a))
sm = sum(x)
if n & 1 == 0 and len([0 for i in a if i < 0]) & 1 == 1:
	sm -= 2 * min(x)
print(sm)


n = int(input())
a = [int(x) for x in input().split()]
count = 0
for i in range(2 * n - 1):
	if a[i] < 0:
		count += 1
if n % 2 == 0 and count % 2 != 0:
	for i in range(2 * n - 1):
		if a[i] < 0:
			a[i] = a[i] * -1
	a = sorted(a)
	a[0] = a[0] * -1
	print(sum(a))
else:
	for i in range(2 * n - 1):
		if a[i] < 0:
			a[i] = a[i] * -1
	print(sum(a))


N = int(input())
A = list(map(int, input().split()))
neg = sum((A[i] < 0 for i in range(len(A))))
if 0 in A or N % 2 == 1:
	neg = 0
B = sorted([abs(A[i]) for i in range(len(A))])
if neg & 1:
	print(-abs(B[0]) + sum((B[i] for i in range(1, len(B), 1))))
else:
	print(sum((B[i] for i in range(len(B)))))


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