There are $n$ slimes in a row. Each slime has an integer value (possibly negative or zero) associated with it.

Any slime can eat its adjacent slime (the closest slime to its left or to its right, assuming that this slime exists). 

When a slime with a value $x$ eats a slime with a value $y$, the eaten slime disappears, and the value of the remaining slime changes to $x - y$.

The slimes will eat each other until there is only one slime left. 

Find the maximum possible value of the last slime.


-----Input-----

The first line of the input contains an integer $n$ ($1 \le n \le 500\,000$) denoting the number of slimes.

The next line contains $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$), where $a_i$ is the value of $i$-th slime.


-----Output-----

Print an only integer — the maximum possible value of the last slime.


-----Examples-----
Input
4
2 1 2 1

Output
4
Input
5
0 -1 -1 -1 -1

Output
4


-----Note-----

In the first example, a possible way of getting the last slime with value $4$ is:

  Second slime eats the third slime, the row now contains slimes $2, -1, 1$

 Second slime eats the third slime, the row now contains slimes $2, -2$

 First slime eats the second slime, the row now contains $4$ 

In the second example, the first slime can keep eating slimes to its right to end up with a value of $4$.

Difficulty: interview

Starter code:

Solutions:
import sys
import string


def ria():
    return [int(i) for i in input().split()]


n = ria()[0]
ar = ria()

if n == 1:
    print(ar[0])
    return

onlyNegs = True
onlyPos = True

if max(ar) >= 0:
    onlyNegs = False
if min(ar) <= 0:
    onlyPos = False

if onlyNegs:
    print(abs(sum(ar)) + max(ar) * 2)
    return

if onlyPos:
    print(abs(sum(ar)) - min(ar) * 2)
    return

print(sum([abs(i) for i in ar]))


n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(a[0])
else:
	prod_minus = False
	for i in range(n - 1):
		if a[i] * a[i + 1] <= 0:
			prod_minus = True
			break
	Min_abs = float("inf")
	Sum = 0
	for num in a:
		Sum += abs(num)
		if abs(num) < Min_abs:
			Min_abs = abs(num)

	if prod_minus:
		print(Sum)
	else:
		print(Sum - 2 * Min_abs)

#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        print(*args, **kwargs, file=sys.stderr)
    dprint('debug mode')
except ModuleNotFoundError:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()

za = getIntList()
if N==1:
    print(za[0])
    return
t1 = max(za)
t2 = min(za)
if t2>=0:
    print(sum(za) - 2*t2)
    return
if t1<=0:
    print(2*t1 - sum(za))
    return

res = 0
for x in za:
    res+= abs(x)

print(res)









import sys
import os

def solve(slimes):
    if len(slimes) == 1:
        return slimes[0]

    havePos = False
    haveNeg = False

    for s in slimes:
        if s > 0:
            havePos = True
        elif s < 0:
            haveNeg = True

    if havePos and haveNeg:
        return sum(map(abs, slimes))
    elif not havePos:
        m = max(slimes)
        return sum(list(map(abs, slimes))) + 2 * m
    elif not haveNeg:
        m = min(slimes)
        return sum(list(map(abs, slimes))) - 2 * m
    else:
        return 0

def main():
    n = int(input())
    slimes = list(map(int, input().split()))
    print(solve(slimes))


def __starting_point():
    main()
__starting_point()

if input()=='1':
 print(input())
else:
 x,*a,y=sorted(map(int,input().split()))
 print(y-x+sum(map(abs,a)))

#Problem D: Slime

n = int(input())

a = input().split()

for i in range(n):
    a[i] = int(a[i])

if(n==1):
    print(a[0]) #Obvious Case
else:
    sm = 0
    havePositive = False
    haveNegative = False

    for c in a:
        if(c==0):
            haveNegative = True
            havePositive = True
        elif(c>0):
            havePositive = True
            sm += c
        else:
            haveNegative = True
            sm -= c

    if(haveNegative and havePositive):
        print(sm) #Final Answer
    else:
        for i in range(n):
            a[i] = abs(a[i])
        #Get the minimum
        ans = sum(a)
        low = a[0]
        for c in a:
            low = min(low,c)
        #Final Answer
        print(ans-2*low)


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

if n==1:
    print(A[0])

elif n==2:
    print(abs(A[0]-A[1]))

else:
    SUM=0
    for i in range(n):
        SUM+=abs(A[i])
    ANS=0

    for i in range(n-1):
        if ANS<SUM-abs(A[i])-abs(A[i+1])+abs(A[i]-A[i+1]):
            ANS=SUM-abs(A[i])-abs(A[i+1])+abs(A[i]-A[i+1])

    print(ANS)


def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())

n = ii()
a = li()
b = [abs(x) for x in a] 
if n == 1:
    ans = a[0]
elif all(x > 0 for x in a) or all(x < 0 for x in a):
    b.sort()
    ans = sum(b) - 2 * b[0]
else:
    ans = sum(b)
print(ans)


n = int(input())
arr = list(map(int, input().strip().split()))
k = min(arr)
h = max(arr)
s = 0
for i in arr:
    if i >= 0:
        s += i
    else:
        s -= i

if n == 1:
    print(arr[0])
elif ((k < 0 and h >= 0)):
    print(s)
else:
    if (k >= 0):
        print(s - 2 * k)
    else:
        print(s + 2 * h)

n = int(input())
xs = [int(x) for x in input().split()]
prefix = [-1 for i in range(n)]
suffix = [-1 for i in range(n)]
prefix[0] = 0
pre_has_neg = [False for i in range(n)]
suffix[-1] = 0
suf_has_neg = [False for i in range(n)]
for i in range(n):
	if i == 0:
		prefix[i] = xs[i]
	else:
		prefix[i] = prefix[i-1] + xs[i]
for i in reversed(range(n)):
	if i == n-1:
		suffix[i] = xs[i]
	else:
		suffix[i] = suffix[i+1] + xs[i]
for i in range(n):
	if i == 0:
		pre_has_neg[i] = xs[i] <= 0
	else:
		pre_has_neg[i] = pre_has_neg[i-1] or xs[i] <= 0
for i in reversed(range(n)):
	if i == n-1:
		suf_has_neg[i] = xs[i] <= 0
	else:
		suf_has_neg[i] = suf_has_neg[i+1] or xs[i] <= 0

prebignum = [None for i in range(n)]
sufbignum = [None for i in range(n)]
for i in range(n):
	if i == 0:
		prebignum[i] = xs[i]
	else:
		prebignum[i] = min(prebignum[i-1], xs[i])
for i in reversed(range(n)):
	if i == n-1:
		sufbignum[i] = xs[i]
	else:
		sufbignum[i] = min(sufbignum[i+1], xs[i])

neg_pre = [100000 for i in range(n)]
neg_suf = [100000 for i in range(n)]

for i in range(n):
	if i == 0:
		neg_pre[i] = min(xs[i], -xs[i])
	else:
		neg_pre[i] = neg_pre[i-1] + min(xs[i], -xs[i])

for i in reversed(range(n)):
	if i == n-1:
		neg_suf[i] = min(xs[i], -xs[i])
	else:
		neg_suf[i] = neg_suf[i+1] + min(xs[i], -xs[i])

ans = -100000000000000000
for i in range(n):
	#print(i, "----")
	tans = xs[i]
	if i == 0:
		pass
	elif pre_has_neg[i-1]:
		tans -= neg_pre[i-1]
	else:
		tans += prefix[i-1]
		tans -= prebignum[i-1]*2

	if i == n-1:
		pass
	elif suf_has_neg[i+1]:
		tans -= neg_suf[i+1]
	else:
		tans += suffix[i+1]
		tans -= sufbignum[i+1]*2
		#print(suffix[i+1], sufbignum[i+1])
	ans = max(ans, tans)

print(ans)

#from random import random, randint
#from sys import stdout

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

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


import math
n=int(input())
arr=list(map(int,input().split()))
cp=0
cn=0
for i in range(len(arr)):
	if arr[i]>=0:
		cp+=1
	else:
		cn+=1
b=[]
for i in range(len(arr)):
	b.append(abs(arr[i]))
m=min(b)
if n==1:
	print(arr[0])
else:
	if cp>0 and  cn>0:
		print(sum(b))
	else:
		nrt=2*(min(b))
		print(sum(b)-nrt)

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

ans = 0
smax = -10**9
smin = 10**9

for i in s:
	if i > smax:
		smax = i
	if i < smin:
		smin = i

f1 = False
f2 = False

for i in s:
	if (not f1) and (i == smax):
		ans += smax
		f1 = True
		continue

	if (not f2) and (i == smin):
		ans -= smin
		f2 = True
		continue

	if i > 0:
		ans += i
	else:
		ans -= i;

print(ans);
  


n = int(input())
arr = list(map(int, input().split()))
if n == 1:
    print(arr[0])
else:
    brr = [abs(i) for i in arr]
    fl = False
    for i in range(n - 1):
        if arr[i] * arr[i + 1] < 0:
            fl = True
    if not fl:
        print(sum(brr) - 2 * min(brr))
    else:
        print(sum(brr))
    
'''
n = int(input())
arra = list(map(int, input().split()))
arrb = list(map(int, input().split()))
arra.sort()
arrb.sort()
a = 0
b = 0
for i in range(2 * n):
    if i % 2 == 0:
        if len(arra) == 0:
            arrb.pop()
        elif len(arrb) == 0 or arra[-1] >= arrb[-1]:
            a += arra[-1]
            arra.pop()
        else:
            arrb.pop()
    else:
        if len(arrb) == 0:
            arra.pop()
        elif len(arra) == 0 or arrb[-1] >= arra[-1]:
            b += arrb[-1]
            arrb.pop()
        else:
            arra.pop()
print(a - b)
'''
'''
n = int(input())
if n == 1 or n == 2:
    print('No')
else: #if n % 2 == 1:
    print('Yes')
    print((n + 1) // 2, end = ' ')
    for i in range(1, n + 1, 2):
        print(i, end = ' ')
    print()
    print(n // 2, end = ' ')
    for i in range(2, n + 1, 2):
        print(i, end = ' ')
'''
'''
n, k = map(int, input().split())
s = input()
d = [0 for _ in range(k)]
for i in s:
    d[ord(i) - ord('A')] += 1
#al = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#for i in 
print(min(d) * k)
'''

n = int(input())
a = [int(w) for w in input().split()]

s = sum(abs(x) for x in a)
if len(a) == 1:
    print(a[0])
elif all(x>0 for x in a) or all(x<0 for x in a):
    print(max(abs(s-2*abs(x)) for x in a))
else:
    print(s)



def mi():
	return map(int, input().split())

n = int(input())
a = list(mi())

cp,cn=0,0
for i in a:
	if i>=0:
		cp+=1
	if i<=0:
		cn+=1
s = 0 
if n==1:
	print (a[0])
	return
for i in a:
	s+=abs(i)
if cn and cp:
	print (s)
else:
	m = -1e100
	for i in a:
		m = max(m,s-2*abs(i))
	print (m)

n=int(input())
l=list(map(int,input().split()))
pos=0
neg=0
w=[]
for i in range(n):
    if l[i]>=0:
        pos+=1
    else:
        neg+=1
    w.append(abs(l[i]))
if n==1:
    print(l[0])
elif neg!=0 and pos==0:
    print(sum(w)-min(w)*2)
elif pos!=0 and neg==0:
     print(sum(w)-min(w)*2)
else:
    print(sum(w))
    


n = int(input())
arr = list(map(int, input().split()))
absArr = list(map(abs, arr))
positiveCount, negativeCount = 0, 0
for num in arr:
    if num > 0:
        positiveCount += 1
    elif num < 0:
        negativeCount += 1
if n == 1:
    print(arr[0])
elif positiveCount == n or negativeCount == n:
    print(sum(absArr) - 2 * min(absArr))
else:
    print(sum(absArr))


n=int(input())
a=list(map(int,input().split()))
a.sort()
x=0
y=0
s=0
if n==1:
    print(a[0])
    return
for i in a:
    if i>0:
        x+=1
    if i<0:
        y+=1
    s=s+abs(i)
if x==n or y==n:
    if x==n:
        print(s-2*a[0])
    if y==n:
        print(s+2*a[n-1])
else:
    print(s)

n = int(input())
lis = list(map(int,input().split()))
if(len(lis))==1:print(lis[0])
else:
    lis.sort()
    a=-lis[0]+lis[-1]
    lis = list(map(abs,lis))
    print(a+sum(lis[1:-1]))

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

if n == 1:
	print(sum(a))
	return

mn = min(a)
mx = max(a)
s = 0

for i in a:
	s += abs(i)

print(s - abs(mn) - abs(mx) + mx - mn)

if input()=='1':
 print(input())
else:
 x,*a,y=sorted(map(int,input().split()))
 print(y-x+sum(map(abs,a)))

n = int(input())

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

if n == 1:
	print(a[0])
elif n == 2:
	print(max(a[0] - a[1], a[1] - a[0]))
else:
	x = min(a)
	y = max(a)
	a = list(map(abs, a))
	print(sum(a) - (2 * min(a) if x * y > 0 else 0))

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

if n == 1:
    print(A[0])
    return

suma = 0
mine = 1000000001
d = False

for i in range(0,n):
    mine = min(mine,abs(A[i]))
    suma += abs(A[i])
    if i > 0 and ((A[i] >=0 and A[i-1] < 0) or (A[i]<0 and A[i-1]>=0)):
        d = True

if d:
    print(suma)
else:
    print(suma-2*mine)