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.



Sample input:
3
-10 5 -4


Sample output:
19

Submission status: Accepted

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

mi = 1e15
cnt = 0
for i in range(N):
  if A[i] < 0:
    cnt += 1
    A[i] = -A[i]
  if mi > A[i]:
    mi = A[i]

Ans = sum(A)
if cnt % 2 == 1:
  Ans -= mi * 2

print(Ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
m = 0
low = abs(l[0])
s = 0
for i in range(n):
  if l[i] < 0:
    l[i] = abs(l[i])
    m += 1
  if low > l[i]:
    low = l[i]
  s += l[i]
if m%2:
  s -= low*2
print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    for i in range(N-1):
        if A[i] < 0:
            A[i] *= -1
            A[i+1] *= -1
    a_sum =sum(A)

    aa = list(map(abs, A))
    return max(a_sum, sum(aa) - 2*min(aa))


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
A = np.array(A).astype(np.int64)
odd_even = np.sum(A<0) %2
absA = np.abs(A)
abssum = np.sum(absA)
if odd_even==1:

    ans = abssum - 2 * np.sort(absA)[0]
else:
    ans  = abssum
print(ans)

Submission status: Accepted

Solution code:


def main():
    n = int(input())
    a = [int(i) for i in input().split()]

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


main()

Submission status: Accepted

Solution code:

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    bsum = 0
    ma = a[0]
    if ma < 0:
        ma = -ma
    count = 0
    for aa in a:
        if aa < 0:
            count += 1
            aa = -aa
        bsum += aa
        if aa < ma:
            ma = aa
    if count % 2 == 0:
        print(bsum)
    else:
        print(bsum-2*ma)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    n = int(readline())
    a = readlist()
    neg_cnt = sum(ai < 0 for ai in a)
    if neg_cnt % 2 == 0:
        print(sum(map(abs, a)))
    else:
        print(sum(map(abs, a)) - 2 * min(abs(ai) for ai in a))


# region template

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        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):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    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 ostream:
    def __lshift__(self, a):
        if a is endl:
            sys.stdout.write(b"\n")
            sys.stdout.flush()
        else:
            sys.stdout.write(str(a))
        return self


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
cout, endl = ostream(), object()

readline = sys.stdin.readline
readlist = lambda var=int: [var(n) for n in readline().split()]
input = lambda: readline().rstrip(b"\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#0WA n==1 mod saikikilimit exit
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
a.sort()
cnt = 0
for i in range(n):
    if a[i] < 0:
        cnt += 1
    if a[i] == 0:
        cnt = -1
res = 0
if cnt == -1:
    for i in range(n):
        res += abs(a[i])
elif cnt % 2 == 0:
    for i in range(n):
        res += abs(a[i])
else:
    if cnt == n:
        for i in range(n-1):
            res += abs(a[i])
        res += a[-1]
    else:
        for i in range(cnt-1):
            res += abs(a[i])
        res +=  max(abs(a[cnt-1])-a[cnt],a[cnt-1]+a[cnt])
        for i in range(cnt+1,n):
            res += abs(a[i])
print(res)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = inpl()

sign = 0
for i in range(N):
    if A[i] < 0:
        sign += 1
        A[i] *= -1
sign %= 2
A.sort()
if sign == 0:
    print(sum(A))
else:
    print(sum(A[1:])-A[0])

Submission status: Accepted

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

Submission status: Accepted

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

MINUS=0

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

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

if MINUS%2==0:
    print(sum(ABS))

else:
    print(sum(ABS)-min(ABS)*2)

Submission status: Accepted

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

check = 0
m = int(1e10)
ans = 0

for i in A:
    ans += abs(i)
    m = min(m, abs(i))
    if i < 0:
        check += 1

if check % 2 == 1:
    ans -= m * 2

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
zetArr = list(map(abs, arr))
minusNum = 0
minZ = min(zetArr)
for e in arr:
    if e < 0:
        minusNum += 1

if minusNum % 2 == 0:
    print(sum(zetArr))
else:
    print(sum(zetArr) - 2 * minZ)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

cnt1 = 0
flag = False
for i in range(N):
    num = A[i]
    if num == 0:
        flag = True
    if num < 0:
        cnt1 += 1
        A[i] = -num

if flag or cnt1 % 2 == 0:
    print sum(A)
else:
    print sum(A) - min(A) * 2

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter
from itertools import product

def main():
    N = II()
    A = LI()
    n_neg = 0
    for a in A:
        if a < 0:
            n_neg += 1
        elif a == 0:
            n_neg = 0
            break
    if n_neg % 2 == 0:
        ans = sum(abs(a) for a in A)
    else:
        A = [abs(a) for a in A]
        A.sort()
        ans = sum(A[1:]) - A[0]

    return ans

print(main())

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
plus=0
zero=0
minus=0
for i in A:
    if i>0:
        plus+=1
    elif i==0:
        zero+=1
    else:
        minus+=1

if zero>0:
    print(sum([abs(i) for i in A]))
else:
    if minus%2==0:
        print(sum([abs(i) for i in A]))
    else:
        B=[abs(i) for i in A]
        print(sum(B)-2*min(B))

Submission status: Accepted

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

cnt_fu = 0

for i in a:
    if i < 0:
        cnt_fu += 1

b = [ abs(x) for x in a ]

if cnt_fu & 1:
    print (sum(b)-min(b)*2)
else:
    print (sum(b) )

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()], dtype = np.int64)

abs_A = np.abs(A)
abs_sum = abs_A.sum()
abs_min = abs_A.min()
negatives = (A < 0).sum()

ans = abs_sum if negatives%2 == 0 else abs_sum - 2*abs_min
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted(LI())
    for i in range(n//2):
        if a[i*2+1] <= 0:
            a[i*2] *= -1
            a[i*2+1] *= -1
        else:
            if a[i*2] * -1 > a[i*2+1]:
                a[i*2] *= -1
                a[i*2+1] *= -1
            break

    return sum(a)


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

nns = len([x for x in a if x < 0])

ans = sum(abs(x) for x in a)
if nns % 2 != 0:
    m = min(abs(x) for x in a)
    ans -= m * 2

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import numpy as np
import sys
from functools import lru_cache
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]

@lru_cache(maxsize=None)
def dp(i, j):
    if i == 0:
        return 0 if j == 0 else -INF
    if j == 0:
        return max(dp(i - 1, 0) + a[i-1], dp(i - 1, 1) - a[i-1])
    else:
        return max(dp(i - 1, 0) - a[i - 1], dp(i - 1, 1) + a[i - 1])


n = I()
a = LI()
print(dp(n, 0))

Submission status: Runtime Error

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import numpy as np
import sys
from functools import lru_cache
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


@lru_cache(maxsize=None)
def dp(i, j):
    if i == 0:
        return 0 if j == 0 else -INF
    if j == 0:
        return max(dp(i - 1, 0) + a[i-1], dp(i - 1, 1) - a[i-1])
    else:
        return max(dp(i - 1, 0) - a[i - 1], dp(i - 1, 1) + a[i - 1])


n = I()
a = LI()


def main():
    print(dp(n, 0))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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_0 == 0:
    if cnt_neg%2 == 0:
        print(law_ans)
    else:
        print(law_ans-2*absminA)
else:
    pritn(law_ans)

Submission status: Runtime Error

Solution code:
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, a)


cnt_neg = 0

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

cnt_0 = A.count(0)

if cnt_0 == 0:
    if cnt_neg%2 == 0:
        print(law_ans)
    else:
        print(law_ans-2*absminA)
else:
    pritn(law_ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
cnt = 0
l3 = abs(a[-3])
l2 = abs(a[-2])
l1 = abs(a[-1])
last = l3 + l2 + l1
if n == 2 and sum(a) >= 0:
    print(abs(sum(a)))
elif n == 2:
    print(max(abs(a[0]),abs(a[1])))
else:
    for i in range(n-3):
        if a[i] < 0:
            a[i] *= -1
            a[i+1] *= -1
        cnt += a[i]
    # +,+,+ or +,-,- or -,-,+ or -,+,-
    #print(cnt,a[-3],a[-2],a[-1])
    if (a[-3] >= 0 and a[-2] >= 0 and a[-1] >= 0) or (a[-3] >= 0 and a[-2] <= 0 and a[-1] <= 0) or (a[-3] <= 0 and a[-2] <= 0 and a[-1] >= 0) or (a[-3] <= 0 and a[-2] >= 0 and a[-1] <= 0):
        print(cnt+last)
    elif (a[-3] <= 0 and a[-2] >= 0 and a[-1] >= 0): # -,+,+
        print(cnt + last - 2*min(l1,l2,l3))
    else:
        print(cnt + last - 2*min(l1,l2))

Submission status: Runtime Error

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

debug = True

while True:
    changed = False
    i = 1
    while i < N - 1:
        if (A[i] > 0) and (A[i - 1] < 0) and (A[i + 1] < 0):
            A[i] = A[i] * -1
            A[i - 1] = A[i - 1] * -1
            changed = True
            if debug: print("change 0:" + str(A))
            i = i + 3
        else:
            i = i + 1
    for i in range(N - 1):
        if (A[i] < 0) and (A[i + 1] < 0):
            A[i] = A[i] * -1
            A[i + 1] = A[i + 1] * -1
            changed = True
            if debug: print("change 1:" + str(A))
    for i in range(N - 1):
        if (A[i] < 0):
            val = A[i] * -1
            if (i > 0):
                if A[i + 1] < A[i - 1]:
                    if val > A[i + 1]:
                        A[i] = A[i] * -1
                        A[i + 1] = A[i + 1] * -1
                        changed = True
                        if debug: print("change 2:" + str(A))
                else:
                    if val > A[i - 1]:
                        A[i] = A[i] * -1
                        A[i - 1] = A[i - 1] * -1
                        changed = True
                        if debug: print("change 3:" + str(A))
            else:
                if val > A[i + 1]:
                    A[i] = A[i] * -1
                    A[i + 1] = A[i + 1] * -1
                    changed = True
                    if debug: print("change 4:" + str(A))
    if (not changed):
        break


print(sum(A))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left,bisect,bisect_right
import sys

icase=1
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)
    sys.exit()

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)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
Aabs=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))

Submission status: Runtime Error

Solution code:
n=int(input())
A=list(map(int,input().split()))
Aabs=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))

Submission status: Runtime Error

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def flip_signs(a,b):
    if A[a] + A[b] < 0:
        A[a] *= (-1)
        A[b] *= (-1)
    elif A[a] + A[b]  == 0:
        if n//2 < a:
            A[b] = abs(A[b])
            A[a] *= A[b]//abs(A[b])
        elif b < n//2:
            A[a] = abs(A[a])
            A[b] *= A[a]//abs(A[a])

if n%2 == 1:
    for i in range(n//2-1):
        flip_signs(i,i+1)
        flip_signs(n-1-i,n-2-i)
    ans = sum(A[:(n//2-1)]+A[(n//2+2):])
    x = A[n//2-1]
    y = A[n//2]
    z = A[n//2+1]
    ans += max([-x-y+z,x-y-z,x+y+z,-x+y-z])

else:
    for i in range(n//2-1):
        flip_signs(i,i+1)
        flip_signs(n-1-i,n-2-i)
    ans = sum(A[:(n//2-1)]+A[(n//2+2):])
    x = A[n//2-1]
    y = A[n//2]
    ans += max(-x-y,x+y)
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())

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

plus = []

minas = []

for value in a:
    if value < 0:
        minas.append(abs(value))
    else:
        plus.append(value)

if len(minas)%2 == 0:
    ans = sum(plus)+sum(minas)
else:
    mini = min(min(plus),min(minas))
    ans = sum(plus)+sum(minas)-mini*2

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
import bisect
a.sort()

idx = bisect.bisect_left(a, 0)
sm = [abs(x) for x in a]
if idx % 2 == 0:
    print(sum(sm))
else:
    print(sum(sm) - 2*min(abs(a[idx]), abs(a[idx-1])))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
import bisect
a.sort()

idx = bisect.bisect_left(a, 0)

if idx % 2 == 0:
    print(sum(abs(a)))
else:
    sm = [abs(x) for x in a]
    print(sum(sm) - 2*min(abs(a[idx]), abs(a[idx-1])))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

idx = bisect_left(A,0)
if idx != 0:
  if idx % 2 == 1:
    if abs(A[idx-1]) > abs(A[idx]):
      A[idx-1] *= -1
      A[idx] *= -1
  for i in range(0,idx-1,2):
    A[i] *= -1
    A[i+1] *= -1

print(sum(A))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
abs_A =  map(lambda x: abs(x), A)

pos = []
neg = []
ans = 0

for e in A:
    if e > 0:
        pos.append(e)
    else:
        neg.append(e)
if len(neg) % 2 == 0:
    ans = sum(abs_A)
else:
    """pos.sort(reverse=True)
    neg.sort(reverse=True)
    if len(neg) == N:
        ans = -sum(neg[:-1]) + neg[-1]
    else:"""
    #ans = max(-sum(neg[:-1]) + neg[-1], -sum(neg[:-3]) + sum(neg[-3:]))
    #ans = max(sum(pos[:-1])-pos[-1]-sum(neg), sum(pos) + neg[0] -sum(neg[1:]))
    ans = sum(abs_A)
    ans -= 2 * min(abs_A)
print(ans)

Submission status: Runtime Error

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

pos = []
neg = []
ans = 0

for e in A:
    if e > 0:
        pos.append(e)
    else:
        neg.append(e)
if len(neg) % 2 == 0:
    ans = sum(pos) - sum(neg)
else:
    """pos.sort(reverse=True)
    neg.sort(reverse=True)
    if len(neg) == N:
        ans = -sum(neg[:-1]) + neg[-1]
    else:"""
    #ans = max(-sum(neg[:-1]) + neg[-1], -sum(neg[:-3]) + sum(neg[-3:]))
    #ans = max(sum(pos[:-1])-pos[-1]-sum(neg), sum(pos) + neg[0] -sum(neg[1:]))
    ans = sum(pos) - sum(neg)
    ans -= 2 * min(min(pos), -max(neg))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
plus = []
minus = []
for a in map(int,input().split()):
    if a>=0:
        plus.append(a)
    else:
        minus.append(a)
ans = sum(plus)-sum(minus)
if len(minus)%2==1:
    ans = ans - 2*min(abs(max(minus)),min(plus))
print(ans)

Submission status: Runtime Error

Solution code:
import collections

N =int(input())

As = [int(item) for item in input().split()]

cnt = 0

Bs = collections.deque()

min1 = 1000000000000

for i in As:

	if As < 0:
      cnt +=1

	Bs.append(abs(i))

	mim1=min(min1, abs(i))

	

if cnt % 2 =0:

	print(sum(list(Bs)))

else:

	print(sum(list(Bs))-min1*2)

Submission status: Runtime Error

Solution code:
import collections

N =int(input())

As = [int(item) for item in input().split()]

cnt = 0

Bs = collections.deque()

min1 = 1000000000000

for i in As:

	if As < 0:		cnt +=1

	Bs.append(abs(i))

	mim1=min(min1, abd(i))

	

if cnt % 2 =0:

	print(sum(list(Bs)))

else:

	print(sum(list(Bs))-min1*2)

Submission status: Runtime Error

Solution code:
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[i][0]がiを選んで反転させない場合の最大値, dp[i][1]がiを選んで反転させた場合の最大値

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]) # iを選んで反転させない時、 i-1を選んで反転させていなかったらiはそのままで、i-1を反転させていたらiは反転する
    dp[i][1] = max(dp[i-1][0]-A[i-1], dp[i-1][1]+A[i-1]) # iを選んで反転させる時、i-1を選んで反転させていなかったらiは反転していて、i-1を反転させていたらiはそのまま

print(dp[n][0]) # nを選ぶことはできない（n+1が存在しない）ため、答えはdp[n][0]

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    n = int(input())
    a = map(int,input().split())
    p = []
    m = []
    for i in a:
        if i >= 0:
            p.append(i)
        else:
            m.append(i)
    if len(m)>=1 and len(m)%2 == 0:
        print(np.sum(p)-np.sum(m))
    else:
        if abs(np.min(p))>=abs(np.max(m)):
            print(np.sum(p)-np.sum(m)+2*np.max(m))
        else:
            print(np.sum(p)-np.sum(m)-2*np.min(p))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    n = int(input())
    a = map(int,input().split())
    p = []
    m = []
    for i in a:
        if i >= 0:
            p.append(i)
        else:
            m.append(i)
    if len(m)>=1 && len(m)%2 == 0:
        print(np.sum(p)-np.sum(m))
    else:
        if abs(np.min(p))>=abs(np.max(m)):
            print(np.sum(p)-np.sum(m)+2*np.max(m))
        else:
            print(np.sum(p)-np.sum(m)-2*np.min(p))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    n = int(input())
    a = map(int,input().split())
    p = []
    m = []
    for i in a:
        if i >= 0:
            p.append(i)
        else:
            m.append(i)
    if len(m)%2 == 0:
        print(np.sum(p)-np.sum(m))
    else:
        if abs(np.min(p))>=abs(np.max(m)):
            print(np.sum(p)-np.sum(m)+2*np.max(m))
        else:
            print(np.sum(p)-np.sum(m)-2*np.min(p))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    if n == 1:
        print(abs(sum(a)))
        exit()

    idx = bisect_right(a, 0)

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


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

Submission status: Runtime Error

Solution code:
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]))
    else:
        print(sum(a[idx:]) - sum(a[:idx]) - 2 * min(-a[idx - 1], a[idx]))


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

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
negative = []
positive = []
cnt=0
for i in range(n):
  if a[i] < 0:
    cnt += 1
    negative.append(a[i])
  else:
    positive.append(a[i])
if cnt % 2 == 0:
  print(sum(map(lambda x: abs(x), a)))
else:
  negative.sort()
  positive.sort()
  if abs(negative[-1]) < positive[0]:
    a.remove(negative[-1])
    print(negative[-1]+sum(map(lambda x: abs(x), a)))
  else:
    a.remove(positive[0])
    print(-positive[0]+sum(map(lambda x: abs(x), a)))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
negative=[]
positive=[]
for ele in a:
    if ele<0:
        negative.append(ele)
    else:
        positive.append(ele)
if len(negative)==0:
    print(sum(a))
else:
    if len(negative)%2==0:
        print(-sum(negative)+sum(positive))
    else:
        if (-1)*negative[-1]>positive[0]:
            print(-sum(negative)+sum(positive[1:])-positive[0])
        else:
            print(-sum(negative[:-1])+sum(positive)+negative[-1])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
negative=[]
positive=[]
for ele in a:
    if ele<0:
        negative.append(ele)
    else:
        positive.append(ele)
if len(negative)==0:
    print(sum(a))
else:
    if len(negative)%2==0:
        print(-sum(negative)+sum(positive))
    else:
        if -negative[-1]>positive[0]:
            print(-sum(negative)+sum(positive[1:])-positive[0])
        else:
            print(-sum(negative[:-1])+sum(positive)+negative[-1])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
negative=[]
positive=[]
for ele in a:
    if ele<0:
        negative.append(ele)
    else:
        positive.append(ele)
if len(negative)==0:
    print(sum(a))
else:
    if len(negative)%2==0:
        print(-sum(negative)+sum(positive))
    else:
        if -negative[-1]>positive[0]:
            print(-sum(negative)+sum(positive[1:])-positive[0])
        else:
            print(-sum(negative[:-2])+sum(positive)+negative[-1])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
negative=[]
positive=[]
for ele in a:
    if ele<0:
        negative.append(ele)
    else:
        positive.append(ele)
if len(negative)==0:
    print(sum(a))
else:
    if len(negative)%2==0:
        print(-sum(negative)+sum(positive))
    else:
        if -negative.back()>positive[0]:
            print(-sum(negative)+sum(positive[1:])-positive[0])
        else:
            print(-sum(negative[:-2])+sum(positive)+negative.back())

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
negative=[]
positive=[]
for ele in a:
    if ele<0:
        negative.append(ele)
    else:
        positive.append(ele)
if len(negative)==0:
    print(sum(a))
else:
    if len(negative)%2==0:
        print(-sum(negative)+sum(positive))
    else:
        if -negative[0]>positive[0]:
            print(-sum(negative)+sum(positive[1:])-positive[0])
        else:
            print(-sum(negative[1:])+sum(positive)+negative[0])