CodeEff/ECCO huggingface dataset:
# Original solution
#配るDPで今度は解いてみる。
n=int(eval(input()))
H=list(map(int,input().split()))
#H[i]はi+1番目の足場の高さ
#dp[n] nまでのminimumコストを選んだときのコスト

dp= [float('inf') for i in range(n+2)]
dp[0]=0
for i in range(n-2):
    dp[i+2]=min(dp[i+2],dp[i]+abs(H[i+2]-H[i]))
    dp[i+1]=min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
#i=n-2
dp[n-1]=min(dp[n-1], dp[n-2]+abs(H[n-1]-H[n-2]))
print((dp[n-1]))

# Optimized solution
#配るDP
#Hの添字は1-indexに変更
n=int(eval(input()))
H=[0]+list(map(int,input().split()))
dp=[10**10]*(n+1)
dp[1]=0
for i in range(1,n):
    if i+2<=n:
        dp[i+2]=min(dp[i]+abs(H[i]-H[i+2]), dp[i+2])
    dp[i+1]=min(dp[i]+abs(H[i]-H[i+1]), dp[i+1])
print((dp[n]))
# Original solution
N = int(eval(input()))
h = list(map(int, input().split()))
dp = [10 ** 10] * N
# dp[n]はあとnのところからのN-1に行くのに支払うコストの最小値
dp[0] = 0
dp[1] = abs(h[N-1]-h[N-2])
for n in range(0, N-2):
    dp[n+2] = min(dp[n+1]+abs(h[(N-1)-(n+2)]-h[(N-1)-(n+1)]),
                  dp[n]+abs(h[(N-1)-(n+2)]-h[(N-1)-n]))
print((dp[N-1]))


# Optimized solution
N = int(eval(input()))
h = list(map(int, input().split()))
a, b = 0, abs(h[0] - h[1])
for n in range(N - 2):
    a, b = b, min(a + abs(h[n] - h[n + 2]), b + abs(h[n + 1] - h[n + 2]))
print(b)
# Original solution
N, K = int(eval(input())), 2
*h, = list(map(int, input().split()))
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print((a[K - 1]))


# Optimized solution
n = int(eval(input()))
*H, = list(map(int, input().split()))
a, b = 0, abs(H[0]-H[1])
for i in range(2, n):
    a, b = b, min(a+abs(H[i]-H[i-2]), b+abs(H[i]-H[i-1]))
print(b)
# Original solution
N = int(eval(input()))
A = [0] + list(map(int, input().split()))

dp = [[0, 0] for _ in range(N+1)]
# dp[i][j]: j=0 -> A[1] + ... + A[i] の MAX
#           j=1 -> A[i] and A[i+1] を反転させた状態での和の最大値

dp[0][0] = 0
dp[0][1] = -float("inf")

for i in range(N):
    dp[i+1][0] = max(dp[i][0] + A[i+1], dp[i][1] - A[i+1])
    dp[i+1][1] = max(dp[i][0] - A[i+1], dp[i][1] + A[i+1])

print((dp[N][0]))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
abss = [abs(A[i]) for i in range(N)]
minus = [A[i] for i in range(N) if A[i] < 0]
if len(minus) % 2 == 0:
    ans = sum([abs(A[i]) for i in range(N)])
    print(ans)
else:
    abss.sort()
    ans = -abss[0] + sum(abss[1:])
    print(ans)
# Original solution
def main():
    N = int(eval(input()))
    A = list(map(int, input().split(" ")))
    negative = 0
    result = 0
    abs_minimum = 10**9
    for a in A:
        abs_minimum = min(abs_minimum, abs(a))
        if a < 0:
            negative += 1
    if negative % 2 == 0:
        for a in A:
            result += abs(a)
    else:
        for a in A:
            if abs(a) == abs_minimum:
                result += min(a, -a)
            else:
                result += abs(a)
    print(result)


if __name__ == '__main__':
    main()

# Optimized solution
def main():
    n = int(eval(input()))
    a = [int(x) for x in input().split()]
    count_negative = 0
    for i in range(n):
        if a[i] < 0:
            count_negative += 1
    a = [abs(x) for x in a]
    answer = sum(a)
    if count_negative % 2:
        answer -= 2 * min(a)
    print(answer)


if __name__ == '__main__':
    main()
# Original solution
from sys import stdin

readline = stdin.readline

_, *aa = list(map(int, open(0).read().split()))
r = 0
mi = 1000000000
m = 0
for a in aa:
    if a < 0:
        m += 1
    b = abs(a)
    r += b
    mi = min(b, mi)
print((r - mi * 2 * (m % 2)))


# Optimized solution
from sys import stdin
 
readline = stdin.readline
 
def main():
    _, *A = list(map(int, open(0).read().split()))
 
    B = tuple(map(abs, A))
    C = tuple(a for a in A if a < 0)
    print((sum(B) - min(B)*2*(len(C)%2)))
 
 
if __name__ == "__main__":
    main()
# Original solution
from sys import stdin

readline = stdin.readline

_, *aa = list(map(int, open(0).read().split()))
r = 0
mi = 1000000000
m = 0
for a in aa:
    if a < 0:
        m += 1
    b = abs(a)
    r += b
    if b < mi:
        mi = b
print((r - mi * 2 * (m % 2)))


# Optimized solution
def main():
    _ = eval(input())
    A = tuple(map(int, input().split()))
 
    B = tuple(map(abs, A))
    C = tuple(a for a in A if a < 0)
    print((sum(B) - min(B)*2*(len(C)%2)))
 
 
if __name__ == "__main__":
    main()
# Original solution
_, *aa = list(map(int, open(0).read().split()))
r = 0
mi = 1000000000
m = 0
for a in aa:
    if a < 0:
        m += 1
    b = abs(a)
    r += b
    if b < mi:
        mi = b
print((r - mi * 2 * (m % 2)))


# Optimized solution
from sys import stdin

readline = stdin.readline

n = readline()
aa = list(map(int, readline().split()))
r = 0
mi = 1000000000
m = 0
for a in aa:
    if a < 0:
        m += 1
    b = abs(a)
    r += b
    if b < mi:
        mi = b
print((r - mi * 2 * (m % 2)))
# Original solution
N = int(eval(input()))
A = [int(x) for x in input().split()]

abs_list = sorted([abs(x) for x in A])[::-1]

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

if abs(min(A)) != min(abs_list):
    A[A.index(min(A))] *= -1
    A[A.index(min(abs_list))] *= -1
    
print((sum(A)))

# Optimized solution
# D

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

minus_num = len([x for x in A if x < 0])
abs_list = [abs(x) for x in A]
if minus_num % 2:
    print((sum(abs_list) - min(abs_list)*2))
else:
    print((sum(abs_list)))
# Original solution
import sys
input = sys.stdin.readline

N = int(eval(input()))
A = list(map(int, input().split()))
cnt = 0
m = 10**18

for Ai in A:
    if Ai<0:
        cnt += 1
    
    m = min(m, abs(Ai))

if cnt%2==0:
    print((sum(abs(Ai) for Ai in A)))
else:
    print((sum(abs(Ai) for Ai in A)-2*m))

# Optimized solution
import sys
input = sys.stdin.readline

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

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

if cnt%2==0:
    print((sum(abs(Ai) for Ai in A)))
else:
    A.sort(key=lambda x: abs(x))
    print((-abs(A[0])+sum(abs(Ai) for Ai in A[1:])))
# Original solution
N = int(eval(input()))
A = list(map(int, input().split(" ")))

while True:
	updated = False
	for i in range(N-1):
		for j in range(i+1, N):
			if (A[i] + A[j] < 0):
				updated = True
				A[i] *= -1
				A[j] *= -1
				updated = True
	if not updated:
		break

print((sum(A)))


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split(" ")))
abs_list = list(map(abs, A))
abs_list.sort()
pos = list([x for x in A if x > 0])
neg = list([x for x in A if x < 0])
pos.sort()
neg.sort()

# A has 0
if abs_list[0] == 0:
	print((sum(abs_list)))
elif len(neg) % 2 == 0:
	print((sum(abs_list)))
elif len(pos) > 0 and abs(pos[0]) < abs(neg[-1]):
	print((sum(abs_list) - 2*pos[0]))
else:
	print((sum(abs_list[1:])-abs_list[0]))
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

nums = A[:]
import math

gcd_queue = [
    (0, nums[0]),
]
for n in nums[1:]:
    tmp_queue = []
    for q in gcd_queue:
        tmp_queue.append((q[0] + q[1], n))
        tmp_queue.append((q[0] + q[1]*-1, n*-1))
    gcd_queue = set(tmp_queue[:])
    #print(gcd_queue)

gcd_queue = list(gcd_queue)
ans = gcd_queue[0][0] + gcd_queue[0][1]
for q in gcd_queue:
    ans = max(ans, q[0]+q[1])
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

nums = A[:]
import math

gcd_queue = [
    (0, nums[0]),
]
for n in nums[1:]:
    tmp_queue = []
    for q in gcd_queue:
        tmp_queue.append((q[0] + q[1], n))
        tmp_queue.append((q[0] + q[1]*-1, n*-1))
    gcd_queue = set(tmp_queue[:])
    #print(gcd_queue)
    tmp = {}
    for q in gcd_queue:
        if str(q[1]) in tmp:
            tmp[str(q[1])] = max(q[0], tmp[str(q[1])])
        else:
            tmp[str(q[1])] = q[0]
    #print(tmp)
    gcd_queue = []
    for k, v in list(tmp.items()):
        #print(k, v)
        gcd_queue.append((v, int(k)))
    

gcd_queue = list(gcd_queue)
ans = gcd_queue[0][0] + gcd_queue[0][1]
for q in gcd_queue:
    ans = max(ans, q[0]+q[1])
print(ans)
# Original solution
# ABC125D - Flipping Signs
def main():
    N = int(eval(input()))
    A = tuple(map(int, input().split()))
    mi = min(abs(i) for i in A)
    abs_sum = sum(abs(i) for i in A)
    neg = sum(i < 0 for i in A)
    if 0 in A or neg % 2 == 0:
        print(abs_sum)
    else:
        print((abs_sum - mi * 2))


if __name__ == "__main__":
    main()

# Optimized solution
# ABC125D - Flipping Signs
def main():
    # neg % 2 == 0 -> all negatives disappear
    # 0 in A -> move all neg there
    # else -> move all neg to the smallest one (abs(i))
    N = int(eval(input()))
    A = tuple(map(int, input().split()))
    mi = min(abs(i) for i in A)
    abs_sum = sum(abs(i) for i in A)
    neg = sum(i < 0 for i in A)
    if 0 in A or neg % 2 == 0:
        print(abs_sum)
    else:
        print((abs_sum - mi * 2))


if __name__ == "__main__":
    main()
# Original solution
# ABC125D - Flipping Signs
def main():
    # neg % 2 == 0 -> all negatives disappear
    # 0 in A -> move all neg there
    # else -> move all neg to the smallest one (abs(i))
    N = int(eval(input()))
    A = tuple(map(int, input().split()))
    mi = min(abs(i) for i in A)
    abs_sum = sum(abs(i) for i in A)
    neg = sum(i < 0 for i in A)
    if 0 in A or neg % 2 == 0:
        print(abs_sum)
    else:
        print((abs_sum - mi * 2))


if __name__ == "__main__":
    main()

# Optimized solution
# ABC125D - Flipping Signs
def main():
    # neg % 2 == 0 -> all negatives disappear
    # 0 in A -> move all neg there
    # else -> move all neg to the smallest one (abs(i))
    N = int(eval(input()))
    A = tuple(map(int, input().split()))
    mi = abs(min(A, key=abs))
    abs_sum = sum(abs(i) for i in A)
    neg = sum(i < 0 for i in A)
    if 0 in A or neg % 2 == 0:
        print(abs_sum)
    else:
        print((abs_sum - mi * 2))


if __name__ == "__main__":
    main()
# Original solution
#!/usr/bin/env python3


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    A.sort()
    ans = sum(A)
    for i in range(0,N-1,2):
        # print(i)
        tmp = ans - 2*(A[i]+A[i+1])
        if tmp > ans:
            ans = tmp
    print(ans)

if __name__ == "__main__":
    main()


# Optimized solution
N = int(eval(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)))
# Original solution
n=int(eval(input()))
a=list(map(int, input().split()))
a_s=sorted(a)
for i in range(0,n-1,2):
    if a_s[i]<0 and a_s[i+1]<0:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    elif a_s[i]<0 and -a_s[i]>a_s[i+1]:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    else:
        break
print((sum(a_s)))

# Optimized solution
n=int(eval(input()))
a=list(map(int, input().split()))
b=list(map(abs, a))
cnt = 0
for i in range(n):
    if a[i]<0:
        cnt+=1
if cnt%2==0:
    print((sum(b)))
else:
    print((sum(b)-2*min(b)))
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
dp=[[0 for _ in range(2)] for _ in range(n+1)]
dp[0][1] = - 10**9
for i in range(n):
  dp[i+1][0]=max(dp[i][0]+a[i],dp[i][1]-a[i])
  dp[i+1][1]=max(dp[i][0]-a[i],dp[i][1]+a[i])
print((dp[n][0]))

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
cnt = sum([1 for i in a if i < 0])
if cnt%2:
  r = 10**9
  for i in range(n):
    r = min(r,abs(a[i]))
  print((sum([abs(x) for x in a])-2*r))  
else:
  print((sum([abs(x) for x in a])))
# Original solution
import sys
sys.setrecursionlimit(1000000)

class Solution():
    def dp(self, pos, sign):
        if pos == self.n-1:
            if sign == 0:
                return +self.lst[pos]
            else:
                return -self.lst[pos]
        elif (pos, sign) in self.vis:
            return self.rcd[pos][sign]
        elif sign == 0:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) + self.lst[pos], self.dp(pos+1, 1) - self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]
        else:
            self.rcd[pos][sign] = max(self.dp(pos+1, 0) - self.lst[pos], self.dp(pos+1, 1) + self.lst[pos])
            self.vis.add((pos, sign))
            return self.rcd[pos][sign]

    def run(self):
        self.n = int(eval(input()))
        self.lst = list(map(int, input().split()))
        self.rcd = [[0, 0] for _ in range(self.n)]
        self.vis = set()
        print((self.dp(0, 0)))

solution = Solution()
solution.run()


# Optimized solution
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_

import sys
sys.setrecursionlimit(1000000)

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

visit = dict()

def dp(pos, sign):
    # terminal condition
    if pos == N-1:
        if sign == 0:
            return A[pos]
        else:
            return -A[pos]

    if (pos, sign) in visit:
        return visit[(pos, sign)]

    elif sign == 0:
        # memorize
        visit[(pos, sign)] = max( dp(pos+1, 0) + A[pos], dp(pos+1, 1) - A[pos])
        return visit[(pos, sign)]

    else: # st == 1
        # memorize
        visit[(pos, sign)] = max( dp(pos+1, 0) -  A[pos], dp(pos + 1, 1) + A[pos])
        return visit[(pos, sign)]

print('{}'.format( dp(0,0) ))
# Original solution
N = int(eval(input()))
A=list(map(int,input().split()))
cnt = 0
B=[None]*N
C=10**9+1
for i in range(len(A)):
  B[i]=abs(A[i])
  C=min(C,B[i])
  if A[i]<0:
    cnt+=1
ret = sum(B)-C+C*(-1)**cnt
print(ret)

# Optimized solution
N = int(eval(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)
# Original solution
int(eval(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]
b.sort()
print((sum(b)-[0,b[0]*2][len(c)%2]))

# Optimized solution
int(eval(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]))
# Original solution
int(eval(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]))

# Optimized solution
n=int(eval(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)))
# Original solution
def main():
    n, *a = list(map(int, open(0).read().split()))
    b = [i for i in a if i <= 0]
    *ab, = [abs(x) for x in a]
    c, d = sum(a), sum(b)
    if len(b) % 2 == 0:
        print((c - 2 * d))
    else:
        print((c - 2 * d - 2 * min(ab)))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    n, *a = list(map(int, open(0).read().split()))
    b = [i for i in a if i <= 0]
    *ab, = list(map(abs, a))
    c = sum(ab)
    if len(b) % 2 == 0:
        print(c)
    else:
        print((c - 2 * min(ab)))


if __name__ == '__main__':
    main()
# Original solution
n = int(eval(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))

# Optimized solution
n=int(eval(input()))
l=list(map(int,input().split()))
m=list(map(abs,l))
print((sum(m)-sum(i<0 for i in l)%2*min(m)*2))
# Original solution
n=int(eval(input()))
a=[*list(map(int,input().split()))]
b=c=0
l=[]
for i in a:
  if i==0:
    b=1
  if i<0:
    c+=1
  l.append(abs(i))
print((sum(l)-[0,min(l)*2][c%2 and b<1]))

# Optimized solution
n=int(eval(input()))
a=[*list(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]))
# Original solution
n=int(eval(input()))
a=[*list(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]))

# Optimized solution
n=int(eval(input()))
l=[*list(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]))
# Original solution
n=int(eval(input()))
l=[*list(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]))

# Optimized solution
n=int(eval(input()))
a=[*list(map(int,input().split()))]
l=[*list(map(abs,a))]
print((sum(l)-sum(i<0 for i in a)%2*min(l)*2))
# Original solution
n=int(eval(input()))
a=[*list(map(int,input().split()))]
l=[*list(map(abs,a))]
print((sum(l)-sum(i<0 for i in a)%2*min(l)*2))

# Optimized solution
eval(input())
a=[*list(map(int,input().split()))]
l=[*list(map(abs,a))]
print((sum(l)-sum(i<0 for i in a)%2*min(l)*2))
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
dp=[[0,0] for i in range(N)]
dp[0][0]=A[0]+A[1]
dp[0][1]=-1*dp[0][0]
for i in range(1,N-1):
    dp[i][0]=max(dp[i-1][0]+A[i+1],dp[i-1][1]+A[i+1])
    dp[i][1]=max(dp[i-1][0]-2*A[i]-A[i+1],dp[i-1][1]+2*A[i]-A[i+1])
print((max(dp[N-2])))

# Optimized solution
N=int(eval(input()))
A=list(map(int,input().split()))
A.sort()
idx=N
for i in range(N):
    if A[i]>0:
        idx=i
        break
if idx==0:
    print((sum(A)))
elif idx==N:
    print((sum(A[(N//2)*2:])-sum(A[:(N//2)*2])))
else:
    x=sum(A[(idx//2)*2:])-sum(A[:(idx//2)*2])
    y=sum(A[((idx+1)//2)*2:])-sum(A[:((idx+1)//2)*2])
    z=sum(A[(1+idx//2)*2:])-sum(A[:(1+idx//2)*2])
    print((max(x,y,z)))
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
b=sum(a)
for i in range(n-1):
    if a[i]<0:
        a[i]=a[i]*(-1)
        a[i+1]=a[i+1]*(-1)
    b=max(b,sum(a))
print((sum(a)))

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
cnt=0
for i in a:
    if i<0:
        cnt+=1
s=0
for i in range(n):
    s+=abs(a[i])
if cnt%2==1:
    c=10**10
    for i in range(n):
        num=abs(a[i])
        if num<c:
            c=num
    s=s-(c*2)
print(s)
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))

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

C = [abs(a) for a in A]
C.sort(reverse=True)
if cnt%2 == 0:
    print((sum(C)))
else:
    C[-1] *= (-1)
    print((sum(C)))

# Optimized solution
n = int(eval(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)
# Original solution
n = int(eval(input()))
a_ls = list(map(int, input().split()))

num_minus = 0
Min = float('inf')
Sum = 0
for i in range(n):
    if a_ls[i] < 0:
        num_minus += 1
    Min = min(abs(a_ls[i]),Min)
    Sum += abs(a_ls[i])
if num_minus % 2 == 0:
    ans = Sum 
else:
    ans = Sum - 2 * Min
print(ans)

# Optimized solution
N = int(eval(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)
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
m = 100000000000
count = 0
ans = 0
for i in range(n):
    if a[i] < 0:
        count += 1
    x = abs(a[i]) 
    ans += x
    m = min(m,x)
if count % 2 != 0:
    ans -= 2*m
print(ans)


# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
m = 10000000000
count = 0
for i in range(n):
    if a[i] < 0:
        count += 1
        a[i] = -a[i]
if count % 2 == 1:
    print((sum(a)-2*min(a)))
else:
    print((sum(a)))
# Original solution
n = int(eval(input()))
a = [int(i) for i in input().split()]
m = sum(1 for i in a if i < 0)
z = any(i==0 for i in a)
if m%2 == 0 or z:
    print((sum(abs(i) for i in a)))
else:
    # print(sum(abs(i) for i in a),min(abs(i) for i in a))
    print((sum(abs(i) for i in a)-2*abs(min(abs(i) for i in a))))


# Optimized solution
N=int(eval(input()))
A=[int(a) for a in input().split()]
ABS_SUM=sum(abs(a) for a in A)
ans=0
if 0 in A:
  ans=ABS_SUM
else:
  pal=sum(1 for a in A if a<0)
  if pal%2==0:
    ans=ABS_SUM
  else:
    ABS_MIN=min(abs(a) for a in A)
    ans=ABS_SUM-ABS_MIN*2
print(ans)
# Original solution
N = int(eval(input()))
A = [int(i) for i in input().split()]

cnt = 0
s = 0
minabs = 10**11
for a in A:
    if a <= -1:
        cnt += 1
    s += abs(a)
    minabs = min(minabs, abs(a))

if cnt % 2 == 0:
    print(s)
else:
    print((s-minabs*2))


# Optimized solution
N = int(eval(input()))
A = [int(i) for i in input().split()]

m = 10**20
c = 0
for a in A:
    if a < 0:
        c += 1
    m = min(m, abs(a))

if c % 2 == 0:
    ans = sum([abs(a) for a in A])
else:
    ans = sum([abs(a) for a in A]) - m*2

print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
ans = 0
m = 10 ** 9 #絶対値の最小
c = 0 #マイナスの数
for i in range(N):
  ans += abs(A[i])
  if m > abs(A[i]):
    m = abs(A[i])
  if A[i] < 0: c += 1
print((ans if c % 2 == 0 else ans - 2 * m))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

cnt = 0
for i in range(N):
    if A[i] < 0:cnt += 1
if cnt % 2 == 0:
    print((sum([abs(x) for x in A])))
else:
    a = [abs(x) for x in A]
    print((sum(a) - min(a)*2))
# Original solution
n=int(eval(input()))
a=[int(i) for i in input().split()]
from itertools import combinations
import copy
b=[i for i in range(n-1)]
c=[v for i in range(1,n) for v in combinations(b, i)]
sum_temp=sum(a)
for v in c:
    a_temp=copy.copy(a)
    for i in v:
        a_temp[i]*=-1
        a_temp[i+1]*=-1
    if sum_temp<sum(a_temp):
        sum_temp=sum(a_temp)
print(sum_temp)

# Optimized solution
n=int(eval(input()))
a=[int(i) for i in input().split()]
ans=None
a_pos=[abs(i) for i in a]
a_min=min(a_pos)
a_neg=sum([1 if i<0 else 0 for i in a])
if a_neg%2==0:
    ans=sum(a_pos)
else: ans=sum(a_pos)-2*a_min
print(ans)
# Original solution
# -*- coding: utf-8 -*-

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

# 正の数p, 負の数nに対して、p+n=N
# 全探索は2^Nで爆発

while True:
    ch = False
    for i in range(0, N-1):
        if i < N-2 and 2*A[i]+3*A[i+1]+2*A[i+2] < 0:
            A[i] *= -1
            A[i+2] *= -1
            ch = True
        if A[i] + A[i+1] < 0:
            A[i] *= -1
            A[i+1] *= -1
            ch = True
    if ch is False:
        break

print((sum(A)))



# Optimized solution
# -*- coding: utf-8 -*-

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

# かっこいい解法版
# Ai, Ai+1を反転して-Ai,-Ai+1であるが、これを繰り返すことで、
# -Ai, Ai+1, Ai+2,....,Aj-1, -Aj というように、
# i < jとなるi,jのみを反転させ、間はそのままという操作が可能。
# ここから、負の数が偶数個であれば、全てを正にすることができる
# 負の数が奇数個であれば、絶対値が一番小さい数を残して残りを正にすればよい

ng = [a for a in A if a < 0]    # 負の数の抽出
ab = [abs(a) for a in A]    # 絶対値の和

if len(ng) % 2 == 0:
    print((sum(ab)))
else:
    mn = min(ab)
    print((sum(ab)-2*mn))
# Original solution
n = int(eval(input()))
A = list(map(int,input().split()))
cnt = 0
for a in A:
    if a < 0:
        cnt += 1
res = 0
A = [abs(a) for a in A]
A.sort()
for a in A:
        res += a
if cnt%2 == 1:
    res -= 2*A[0]
print(res)

# Optimized solution
n = int(eval(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)