Problem:
 Score : 400 points    Problem Statement 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 1 3
-10 5 -4      Sample Output 1 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.       Sample Input 2 5
10 -4 -8 -11 3      Sample Output 2 30       Sample Input 3 11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000      Sample Output 3 10000000000  The output may not fit into a 32 -bit integer type.

Solution (Python):

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n = I()
a = LI()

dp = [[0] * 2 for _ in range(n + 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], dp[i][1] - a[i])  
    dp[i + 1][1] = max(dp[i][0] - a[i], dp[i][1] + a[i])  
print(dp[n][0])

Solution (Python):
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n = I()
a = LI()


cnt = [0, 0, 0]  
for i in a:
    if i < 0:
        cnt[1] += 1
    elif i > 0:
        cnt[0] += 1
    else:
        cnt[2] += 1
if cnt[1] % 2 == 0 or cnt[2] > 0:
    ans = 0
    for i in a:
        ans += abs(i)
else:
    
    ans = 0
    for i in a:
        ans += abs(i)
    ans += -2 * min(abs(i) for i in a)
print(ans)

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

ans = 0
min_a = 10**9+1
flg = False
for i in range(n):
    ans += abs(a[i])
    if a[i] <= 0:
        flg = not flg
    min_a = min(min_a, abs(a[i]))

if flg:
    ans -= 2*min_a

print(ans)

Solution (Python):
import sys
import math
from collections import deque

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 make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


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


if __name__ == "__main__":
    main()

Solution (Python):


import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    a = na()
    a_abs = list()
    zero = False
    minus = 0
    for ai in a:
        if ai < 0:
            minus += 1
        elif ai == 0:
            zero = True
        a_abs.append(abs(ai))
    
    if minus % 2 == 0 or zero:
        print(sum(a_abs))
    else:
        print(sum(a_abs) - 2 * min(a_abs))
        

if __name__ == "__main__":
    main()

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

if 0 in A:
    ans = 0
    for i in range(N):
        ans += max(A[i], -A[i])
    print(ans)
    exit()
    
minus_count = 0
for i in range(N):
    if A[i] < 0:
        minus_count += 1
        
if minus_count % 2 == 0:
    ans = 0
    for i in range(N):
        ans += max(A[i], -A[i])
    print(ans)
else:
    for i in range(N):
        if A[i] < 0:
            A[i] = -A[i]
    min_A = min(A)
    print(sum(A) - 2*min_A)

Solution (Python):
N = int(input())

array = [int(i) for i in input().split()]
calc_array = []

cnt = 0

for n in array:
    if n < 0:
        cnt += 1
    calc_array.append(abs(n))
        
if cnt % 2 == 0 or 0 in calc_array:
    output = sum(calc_array)
else :
    output = sum(calc_array) - (2*min(calc_array))
    
print(output)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n = int(input())
A = list(map(int, input().split()))
INF = 10**9

dp = [[0]*2 for _ in range(n+1)] 

dp[0][0] = 0 
dp[0][1] = -INF

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]-A[i-1], dp[i-1][1]+A[i-1]) 

print(dp[n][0])

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

DP = [[0, 0] for _ in range(n + 1)]
DP[0][1] = -1e20

for i in range(n):
    for j in [0, 1]:
        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[-1][0])

Solution (Python):
import numpy as np

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

cnt = np.sum(np.where(np.array(A) < 0, True, False))



A = list(map(lambda x:abs(x), A))


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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

flip_a = [0]*n
cnt_minus = 0

for i in range(n):
	if a[i] < 0:
		cnt_minus += 1
		flip_a[i] = -a[i]
	else:
		flip_a[i] = a[i]

flip_a.sort()

if cnt_minus%2 == 1:
	flip_a[0] = -flip_a[0]

print(sum(flip_a))

Solution (Python):
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)

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

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

b.sort()
if c%2 == 1:
	b[0] = -b[0]
print(sum(b))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
INF = 10**9

dp0 = [0]
dp1 = [-INF-1]

for i, x in enumerate(A):
  dp0.append( max(dp0[i] + x, dp1[i] - x) )
  dp1.append( max(dp0[i] - x, dp1[i] + x) )

print(dp0[-1])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
INF = 10**9

dp0 = [0]
dp1 = [-INF-1]

for i, x in enumerate(A):
  dp0.append( max(dp0[i] + x, dp1[i] - x) )
  dp1.append( max(dp0[i] - x, dp1[i] + x) )

print(dp0[-1])

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
dp = [[0,0] for _ in range(N+1)]
dp[0][1] = -float('inf')
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]-A[i-1],dp[i-1][1]+A[i-1])
print(dp[-1][0])

Solution (Python):
n=int(input())
a=[0]*n
a=map(int,input().split())
    
z=0
result=0
min=1000000002

for i in a:
    if i<0:
        z+=1
    result+=abs(i)
    if abs(i)<min:
        min=abs(i)

if z%2==1:
    result-=min*2

print(result)

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

total_minus_num = 0
B = []
for a in A:
    if a < 0:
        total_minus_num += 1
    B.append(abs(a))

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

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    DP = [[-10 ** 20, -10 ** 20] for _ in range(N)] 
    DP[0] = [A[0], -1 * 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])
    


    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import numpy as np

N = int(input())

A = list(map(int, input().split()))
A = np.array(A)
A_abs = np.abs(A)
M = np.sum(A_abs)
m = np.min(A_abs)

if np.sum(A < 0) % 2 == 0:
	print(M)
else:
	print(M - 2 * m)

Solution (Python):
import sys
input = sys.stdin.readline

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

tmp = 0
zero = False
B = []
for a in A:
    if a < 0:
        tmp += 1
    elif a == 0:
        zero = True
    B.append(abs(a))

if tmp % 2 == 0 or zero:
    ans = sum(B)
else:
    ans = sum(B) - 2*min(B)

print(ans)

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

minus=[]
abses=[]
cnt=0
for i in range(n):
    if a[i]<0:
        minus.append(1)
    elif a[i]>0:
        minus.append(0)
    else:
        minus.append(0)
        cnt+=1
    abses.append(abs(a[i]))

if sum(minus)%2==0:
    print(sum(abses))
else:
    if cnt>0:
        print(sum(abses))
    else:
        print(sum(abses)- 2*min(abses))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
c = 0
k = 0
for i in range(N):
    if A[i] < 0:
        c += 1
        A[i] *= -1
    elif A[i] == 0:
        k = 1

if c % 2 == 0:
    print(sum(A))
elif k == 1:
    print(sum(A))
else:
    print(sum(A)-2*min(A))

Solution (Python):
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)

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

num_minus = [a < 0 for a in A].count(True)

B = [abs(a) for a in A]

if num_minus%2 == 0:
    print(sum(B))
else:
    b = sorted(B)[0]
    print(sum(B) - 2*b)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
isMinus = False
for i in range(N):
    if A[i] < 0:
        isMinus = not isMinus
        A[i] = A[i]*-1

if isMinus:
    print(sum(A)-min(A)*2)
else:
    print(sum(A))

Solution (Python):


from functools import reduce

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = II()
    A = LII()
  
    mn = 10 ** 9
    n = 0
    ans = 0
    for a in A:
        ans += abs(a)
        mn = min(mn, abs(a))
        if a < 0:
            n += 1

    if n % 2 == 0:
        print(ans)
    else:
        print(ans - 2 * mn)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))
def fde(): print("-flag-")

def main():
    N=ii()
    A=list(mi())
    
    dp = [[0]*2 for _ in range(10**5+10)]
    dp[0][0] = A[0]+A[1]
    dp[0][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]))



if __name__ == "__main__":
    main()

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

Flag = False
cnt = 0
S = 0
m = 10**9

for i in A:
  if i == 0:
    Flag = True
  elif i > 0:
    S += i
    m = min(m, i)
  else:
    S += -i
    cnt ^= 1
    m = min(m, -i)

if Flag or cnt == 0:
  print(S)
else:
  print(S-2*m)

Solution (Python):
N = int(input())
A_list = [int(e) for e in input().split()]









min_abs_A = 7 + 10**9
cnt_minus_in_A = 0
sum_abs_A = 0

for A in A_list:
    if A < 0:
        cnt_minus_in_A += 1
        
    if abs(A) < min_abs_A:
        min_abs_A = abs(A)
    
    sum_abs_A += abs(A)
    
if cnt_minus_in_A % 2 == 0:
    print(sum_abs_A)
else:
    print(sum_abs_A - 2*min_abs_A)

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]

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

a.sort()

if cnt % 2 != 0:
    a[0] *= -1

print(sum(a))

Solution (Python):
N = int(input())
A = map(int, input().split())

A_plus = []
A_minus = []

for a in A:
    if a >= 0:
        A_plus.append(a)
    else:
        A_minus.append(a)

A_plus = sorted(A_plus)
A_minus = sorted(A_minus)


if len(A_minus) % 2 == 0:
    res = sum(A_plus) - sum(A_minus)
else:
    if len(A_plus) > 0:
        res = sum(A_plus) - sum(A_minus) - 2*min(A_plus[0], (-1)*A_minus[-1])
    else:
        res = sum(A_plus) - sum(A_minus) + 2*A_minus[-1]

print(res)

Solution (Python):
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
abs_A = abs(A)

min_A = min(abs_A)

if (A < 0).sum() % 2:
    print(sum(abs_A) - min_A * 2)
else:
    print(sum(abs_A))

Solution (Python):
import heapq
n=int(input())
a=list(map(int,input().split()))

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

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

if zero_count==1 or minus_count%2==0:
    ans=sum(a)
else:
    heapq.heapify(a)
    mn=heapq.heappop(a)
    ans=sum(a)-mn

print(ans)

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

minuscount = 0
for i in range(0,N,1):
    if A[i] < 0:
        minuscount +=1
    if A[i]==0:
        minuscount = 0
        break

ans = 0
for i in range(0,N,1):
    ans += abs(A[i])

minabs = 10**10
if minuscount % 2 !=0:
    for i in range(0,N,1):
        minabs = min(minabs,abs(A[i]))
    ans -= 2*minabs

print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A.sort()
count=0
zer=0
for i in range(N):
  if A[i]<0:
    count+=1
  if A[i]==0:
    zer+=1
ans=0
if zer!=0:
  for i in range(N):
    if A[i]<0:
      A[i]=-A[i]
    ans+=A[i]
else:
  if count%2==0:
    for i in range(N):
      if A[i]<0:
        A[i]=-A[i]
      ans+=A[i]
  else:
    for i in range(N):
      A[i]=abs(A[i])
    A.sort()
    ans=sum(A[1:])-A[0]
print(ans)

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

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

min_abs = float('inf')
cnt = 0
for i in range(n):
    if a[i] < 0:
        cnt += 1
        a[i] *= -1
    min_abs = min(min_abs, a[i])

if cnt % 2 == 0:
    print(sum(a))
else:
    print(sum(a) - 2 * min_abs)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    cnt = 0
    total = 0
    mi = f_inf
    for a in A:
        total += abs(a)
        if a < 0:
            cnt += 1
        if mi > abs(a):
            mi = abs(a)

    if cnt % 2 == 0:
        print(total)
    else:
        print(total - mi * 2)


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

    dp = [[0 for _ in range(2)] for _ in range(n + 1)]
    dp[0][1] = -f_inf
    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] - A[i - 1], dp[i - 1][1] + A[i - 1])

    print(dp[n][0])


if __name__ == '__main__':
    resolve2()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    cnt = 0
    total = 0
    mi = f_inf
    for a in A:
        total += abs(a)
        if a < 0:
            cnt += 1
        if mi > abs(a):
            mi = abs(a)

    if cnt % 2 == 0:
        print(total)
    else:
        print(total - mi * 2)


if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
absA = [abs(a) for a in A]

if sum(True if a < 0 else False for a in A) % 2 == 0:
  ans = sum(absA)
else:
  ans = sum(absA) - 2 * min(absA)
  
print(ans)

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

minus = 0
x = abs(A[0])
cnt = 0
for a in A:
    minus += (a < 0)
    a = abs(a)
    x = min(x, a)
    cnt += a

if x == 0:
    ans = cnt
elif minus % 2 == 0:
    ans = cnt
else:
    ans = cnt - 2 * x
print(ans)

Solution (Python):
def minus(n):
  if n>=0:
    return 0
  else:
    return 1
N=int(input())
L=list(map(int,input().split()))
c=sum(list(map(minus,L)))
if c%2==0:
  t=sum(list(map(abs,L)))
  print(t)
else:
  L=list(map(abs,L))
  print(sum(L)-min(L)*2)

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

min_idx = 0
min_val = float('inf')

for i, a in enumerate(A):
    if abs(a) < min_val:
        min_idx = i
        min_val = abs(a)


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


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


print(sum(A))

Solution (Python):
import sys

input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
m = 0
zero = 0
ans = 0
odd = 10**9
for i in A:
    if i < 0:
        m += 1
    if i == 0:
        zero = 1
    ans += abs(i)
    if odd > abs(i):
        odd = abs(i)
if m %2 == 0 or zero:
    print(ans)
else:
    print(ans-odd*2)

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

B = A.copy()

K = 0

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

Tashita = sum(B)

if K%2 != 0:
	Tashita-=2*min(B)

print(Tashita)

Solution (Python):
import collections

n = int(raw_input())
elems = map(int, raw_input().split(' '))
a = min(map(abs, elems))
s = sum(map(abs, elems))
count = 0
for c in elems:
	if c < 0: count +=1		
a = a if count % 2 else 0

print s - 2*a
"""
+++++----+++

obs 1
if the connected component has || even cardinality % 2==0


obs 2
if the connected component has odd cardinality I can reduce it to 1 
and move the - sign around 

obs 3
as I can move things around, I can merge ccs 


a = 0 if even number of negative signs else min([|v| for v in nums])
return sum([abs(v) for v in nums]) - a

"""

Solution (Python):
import sys
import time




import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
cnt=0
for i in a:
    if i<0:
        cnt+=1
if cnt%2==0:
    print(sum(map(abs,a)))
else:
    print(sum(map(abs,a))-2*min(map(abs, a)))

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

Solution (Python):
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))

cnt = 0
S = 0
minA = 10 ** 9
for a in A:
    if a < 0:
        cnt += 1
    minA = min(minA, abs(a))
    S += abs(a)

if cnt % 2 == 0:
    res = S
else:
    res = S - 2 * minA

print(res)

Solution (Python):
def solve():
    N = int(input())
    A = list(map(int,input().split()))

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

    abs_sum = sum(map(abs,A))
    if n_negative % 2 == 0:
        print(abs_sum)
    else:
        print(abs_sum - 2 * min(map(abs,A)))

if __name__ == '__main__':
    solve()

Solution (Python):
n= int(input())
a = list(map(int,input().split()))
mc = 0
mi = 999999999
hasz=False
for i in range(n):
    if a[i]==0:hasz=True
    else:
        if a[i]<0:
            mc+=1
            a[i]*=-1
        mi = min(mi,a[i])
if hasz or mc%2==0:print(sum(a))
else:print(sum(a)-mi*2)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
"""
マイナスの数偶数→いける
マイナスの数奇数→１こあまる
"""
b = [abs(a[i]) for i in range(n)]


"""
マイナスの個数は
"""
tmp = 0
for i in a:
	if i < 0:
		tmp += 1

if tmp % 2 == 0:
	print(sum(b))
else:
	sumb = sum(b)
	ans = 0
	for i in range(n):
		ans = max(sumb-2*b[i], ans)
	print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mi = float('INF')
t=0
for i in range(n):
    if abs(a[i])<mi:
        mi=abs(a[i])
        t=i
a1=a.copy()
sum1=0
for i in range(n-2):
    if a1[i]<0:
        sum1+=a1[i]*(-1)
        a1[i+1]*=-1
    else:
        sum1+=a1[i]
if a1[n-2]+a1[n-1]>(a1[n-2]+a1[n-1])*(-1):
    sum1+=a1[n-2]+a1[n-1]
else:
    sum1+=(a1[n-2]+a1[n-1])*(-1)

sum2=0
for i in range(n-2):
    if i==t and a[i]<0:
        sum2+=a[i]
        continue
    elif i==t and a[i]>0:
        sum2-=a[i]
        a[i+1]*=-1
        continue
    if a[i]<0:
        sum2+=a[i]*(-1)
        a[i+1]*=-1
    else:
        sum2+=a[i]
if a[n-2]+a[n-1]>(a[n-2]+a[n-1])*(-1):
    sum2+=a[n-2]+a[n-1]
else:
    sum2+=(a[n-2]+a[n-1])*(-1)
print(max(sum1,sum2))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
for i in range(n-1):
    if a[i] > 0:
        pass
    else:
        a[i] *= -1
        a[i+1] *= -1
if a[-1] < 0:
    a[-1] *= -1
    a = sorted(a)
    ans = sum(a) - 2*a[0]
else:
    ans = sum(a)
print(ans)

Solution (Python):
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])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
neg_cnt = sum(a < 0 for a in A)
A = sorted(a if a >= 0 else -a for a in A)
if neg_cnt % 2:
    print(sum(A) - 2 * A[0])
else:
    print(sum(A))

Solution (Python):
import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])
if 0 in a or len(a[a < 0]) % 2 == 0:
    print(int(np.abs(a).sum()))
else:
    m = np.abs(a).min()
    print(int(np.abs(a).sum() - 2 * m))

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

if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
arr=list(map(int,input().split()))

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


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

Solution (Python):

n, *s = map(int, open(0).read().split())
v = list(map(lambda x: abs(x), s))
c = 0
for i in s:
    c += i < 0
if c % 2 == 0:
    print(sum(v))
else:
    print(sum(v) - 2*min(v))

Solution (Python):

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

ans = 0
s = 0
m = float('inf')

for i in A:
    i = abs(i)
    s += i
    m = min(m, i)

minus_num = len(list(filter(lambda x: x < 0, A)))

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

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
count = 0
for i in range(N):
    if A[i] < 0:
        count += 1
    A[i] = abs(A[i])

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

Solution (Python):
import numpy as np
import heapq

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

if len([i for i in A if i < 0]) % 2 == 0:
    A = np.abs(A)
    ans = sum(A)
else:
    A = np.abs(A)
    A = list(A)
    heapq.heapify(A)
    a = heapq.heappop(A)
    ans = sum(A) - a
print(ans)

Solution (Python):
n = int(input())
ls = list(map(int,input().split()))
p = 0
k = float("inf")
q = 0
for i in range(n):
  p += abs(ls[i])
  if k > abs(ls[i]):
    k = abs(ls[i]) 
di = [e for e in ls if e <= 0]
if len(di) % 2== 0:
  print(p)
else:
  print(p-2*k)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
p = sum(ai < 0 for ai in a)
ans = sum(map(abs, a))
if p & 1:
    ans -= 2 * min(abs(ai) for ai in a)
print(ans)

Solution (Python):
N = int(input())
A = [0] + list(map(int, input().split()))

dp = [[0, 0] for _ in range(N+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])

Solution (Python):
from sys import stdin, setrecursionlimit
from bisect import bisect_right


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    idx = bisect_right(a, 0)

    if idx % 2 == 0:
        print(sum(a[idx:]) - sum(a[:idx]))
    elif idx == n:
        print(a[idx - 1] - sum(a[:idx - 1]))
    else:
        print(sum(a[idx:]) - sum(a[:idx]) - 2 * min(-a[idx - 1], a[idx]))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    pa = [abs(a) for a in A]

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):



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

if __name__ == "__main__":
    main()

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

minus_cnt = 0
for i in range(n):
  if a[i] < 0:
    minus_cnt += 1
    a[i] *= -1
  
s = sum(a)
a.sort()
if(minus_cnt % 2 == 1):
  s -= a[0] * 2

print(s)

Solution (Python):

n = int(input())
a = list(map(int,input().split()))
aabs = [i if i>=0 else i*(-1) for i in a]
MIN = min(aabs)
ans = 0
mcount = 0

for i in range(n):
  if a[i] < 0:
    mcount += 1
    
if mcount%2 == 0:
  for i in a:
    ans += abs(i)
  print(ans)
else:
  for i in a:
    ans += abs(i)
  print(ans - 2*MIN)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
aabs = [i if i>=0 else i*(-1) for i in a]
MIN = min(aabs)
ans = 0
mcount = 0

for i in range(n):
  if a[i] < 0:
    mcount += 1
    
if mcount%2 == 0:
  for i in a:
    ans += abs(i)
  print(ans)
else:
  for i in a:
    ans += abs(i)
  print(ans - 2*MIN)

Solution (Python):
import sys

N = int(sys.stdin.readline().strip())
A = map(int, sys.stdin.readline().strip().split())

ans = 0
neg_count = 0
zero_count = 0
a_min = float("inf")
for a_i in A:
    ans += abs(a_i)
    a_min = min(a_min, abs(a_i))
    if a_i == 0:
        zero_count += 1
    elif a_i < 0:
        neg_count += 1


if neg_count % 2 == 0 or zero_count > 0:
    print(ans)
else:
    
    print(ans - 2 * a_min)

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n = i_input()
    num_list = i_list()

    hifu_count = 0
    zero_count = num_list.count(0)

    for num in num_list:
        if num < 0:
            hifu_count += 1

    count = 0
    for num in num_list:
        count += abs(num)

    if zero_count >= 1 or hifu_count % 2 == 0:
        pass
    else:
        min_num = INF
        for num in num_list:
            min_num = min(min_num, abs(num))
        count -= min_num * 2
        
    print(count)

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, stdout
input = stdin.readline
print = stdout.write
n = int(input())
arr = [int(i) for i in input().split()]
sm = sum(abs(i) for i in arr)
mn = min(abs(i) for i in arr)
nc = sum(i < 0 for i in arr)
if nc % 2 == 0: print(str(sm))
else: print(str(sm - 2 * mn))

Solution (Python):
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
ans=sum(np.abs(a))
if 0 in a:
    print(ans)
else:
    b=np.where(a<0)
    if np.size(b)%2==0:
        print(ans)
    else:
        ans-=2*min(np.abs(a))
        print(ans)

Solution (Python):



import sys
readline = sys.stdin.readline

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

ans = 0
minabs = 10 ** 9 + 1
haszero = False
minuscnt = 0
for i in range(len(A)):
  if A[i] == 0:
    haszero = True
  elif A[i] < 0:
    minuscnt += 1
  ans += abs(A[i])
  if abs(A[i]) < minabs:
    minabs = abs(A[i])
    
if haszero:
  print(ans)
elif minuscnt % 2 == 1:
  print(ans - minabs * 2)
else:
  print(ans)

Solution (Python):
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)

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

minus = 0

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


ans = 0
minA = float('inf')
for a in A:
    ans += abs(a)
    if minA > abs(a):
        minA = abs(a)

if 0 in A or minus % 2 == 0:
    print(ans)
    exit(0)

ans -= 2 * minA
print(ans)

Solution (Python):

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

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

    

if A[N-1] >= 0:
    print(sum(A))
    exit()

A = A[::-1]
A[0] *= -1
idx = A.index(min(A))

A[0] *= -1

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

    
    
print(sum(A))

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

Solution (Python):
from statistics import median


from fractions import gcd
from itertools import combinations 
from collections import deque
from collections import defaultdict
import bisect










import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
minus = 0
for i in range(n):
    if A[i] < 0:
        minus += 1
A = sorted(A,key = lambda x:abs(x))


sumA = sum(list(abs(v) for v in A))

if minus % 2:
    print(sumA - abs(A[0])*2)
else:
    print(sumA)

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

mns = len([i for i in A if i < 0])

if mns % 2 == 0:
  ans = sum([abs(i) for i in A])
else:
  ans = sum([abs(i) for i in A]) - 2 * min([abs(i) for i in A])
  
print(ans)

Solution (Python):
n = int(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))

Solution (Python):
def resolve():
    N = int(input())
    A = [0]+list(map(int, input().split()))
    dp = [[None for _ in range(2)] for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = -float("inf")
    for i in range(1, N+1):
        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][0])



if '__main__' == __name__:
    resolve()