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: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()]).astype('int64')

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

print(np.sum(a))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

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

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

print(sum(A))

Submission status: Wrong Answer

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

i = 0
next_compute = True
include_zero = False
sum_a = 0
while (i < N):
    # print(next_compute)
    if i == N - 1:
        if include_zero:
            sum_a = abs(A[i])
        elif next_compute:
            sum_a += A[i]
        else:
            sum_a += (-A[i])
        break
    sum_a += abs(A[i])
    if 0 == A[i]:
        include_zero = True
    elif 0 < A[i] and next_compute:
        # print(str(i) + ': a ' + str(A[i]))
        next_compute = True
    elif 0 < A[i] and not next_compute:
        # print(str(i) + ': b ' + str(A[i]))
        next_compute = False
    elif A[i] < 0 and next_compute:
        # print(str(i) + ': c ' + str(A[i]))
        next_compute = False
    else:
        # print(str(i) + ': d ' + str(A[i]))
        next_compute = True
    i += 1

i = N - 1
prev_compute = True
include_zero = False
sum_a_r = 0
while (0 <= i):
    if i == 0:
        if include_zero:
            sum_a_r += abs(A[i])
        elif prev_compute:
            sum_a_r += A[i]
        else:
            sum_a_r += (-A[i])
        break
    sum_a_r += abs(A[i])
    if 0 == A[i]:
        include_zero = True
    elif 0 < A[i] and prev_compute:
        prev_compute = True
    elif 0 < A[i] and not prev_compute:
        prev_compute = False
    elif A[i] < 0 and prev_compute:
        prev_compute = False
    else:
        prev_compute = True
    i -= 1

# print(sum_a)
# print(sum_a_r)
if sum_a < sum_a_r:
    print(sum_a_r)
else:
    print(sum_a)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
for i in range(0,N-1):
    if (a[i] < 0 and abs(a[i]) > abs(a[i+1])) or (a[i] < 0 and a[i+1] < 0):
        a[i] *= -1
        a[i+1] *= -1
print(sum(a))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N):
    if A[i] <= 0:
        count += 1
ans = 0
if count%2 == 0:
    for i in range(N):
        ans += max(A[i],-A[i])
else:
    tmp = -1000000000
    c = 0
    for i in range(N):
        if tmp < min(A[i],-A[i]) < 0:
            tmp = min(A[i],-A[i])
            c = i
    if tmp == -1000000000 and c == 0:
        if tmp != A[0]:
            tmp = 0
            c = A.index(0)
    
    for i in range(N):
        if i != c:
            ans += max(A[i],-A[i])
        else:
            ans += tmp
print(ans)

Submission status: Wrong Answer

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

for i in range(N-1):
    if B[i] < 0:
        B[i] *= -1
        B[i+1] *= -1
    if B[i] == 0 and B[i+1] < 0:
        B[i+1] *= -1
 
flag = False
for i in range(N):
    if B[i] < 0:
        flag = True
  
res = 0
if flag:
    B.sort()
    for i in range(1, N):
        res += abs(B[i])

    res += B[0]
else:
    for i in range(N):
        res += abs(A[i])
        
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [abs(i) for i in A]
for i in range(N-1):
    if(A[i]<0):
        A[i] = -A[i]
        A[i+1] = -A[i+1]
if(A[N-1]<0):
    flag = False
else:
    flag = True

if(flag):
    print(sum(A))
else:
    m = min(B)
    print(sum(B)-m)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
aa=list(map(int,input().split()))
aa.append(0)
aaa=tuple(aa)
a=list(aaa)
for i in range(n-1):
    if a[i]<0:
        a[i]=-1*a[i]
        a[i+1]=-1*a[i+1]
b=list(aaa)
for i in range(n,0,-1):
    if b[i]<0:
        b[i]=-1*b[i]
        b[i-1]=-1*b[i-1]

print(max(sum(a),sum(b),sum(aa)))

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int,input().split()))
ans = 0

for i in range(n - 1):
    if (((li[i] * -1) + (li[i] * -1)) >= (li[i] + li[i + 1])):
        li[i] *= -1
        li[i + 1] *= -1

for i in range(n):
    ans += li[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl
import fractions
from functools import reduce
import copy
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())
su = 0

a = l()

co = 0
k = 0
a.sort()
f = 0
for i in range(n):
	if a[i] <= 0:
		co += 1
if co % 2 == 0:
	for i in range(n):
		su += abs(a[i])
	print(su)
else:
	for i in range(n):
		if f == 2:
			break
		if a[i] >= 0 and f == 0:
			kk = a[i-1]
			f = 1
		if a[i] >= 0:
			if abs(a[-1]) >= a[i]:
				k = a[i]*-2
			else:
				k = kk*2
			f = 2
		elif i == n-1:
			k = a[i]*2
	for i in range(n):
		su += abs(a[i])
	su += k
	print(su)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [abs(i) for i in A]
for i in range(N-1):
    if(A[i]<0):
        A[i] = -A[i]
        A[i+1] = -A[i+1]
if(A[N-1]<0):
    flag = False
else:
    flag = True

if(flag):
    print(sum(A))
else:
    m = min(B)
    print(sum(B))

Submission status: Wrong Answer

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

a.sort()
if n % 2 == 0:
    ans = sum(a)
else:
    ans = sum(a) - (a[0]*2)
print(ans)

Submission status: Wrong Answer

Solution code:
A=int(input())
B=[_ for _ in map(int,input().split())]
"マイナスの数を求める"
minus=0
for i in B:
  if i<=0:
    minus=+1
"マイナスの数が偶数の場合、絶対値Bを全部足す"
ans=0
if minus%2==0:
  for i in B:
    if i<=0:
      ans=+(-1)*i
    else:
      ans+=i
  print(ans)

else:
  S=0
  for i in range(A):
    B[i]=abs(B[i])
    
  for i in B:
    S+=i
  print(S-2*min(B))

Submission status: Wrong Answer

Solution code:
# D

N = int(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
    
tmp = []
for i in reversed(range(0, N-1)):
    A[i] *= -1
    A[i+1] *= -1
    tmp.append(sum(A))
    
print(max(tmp))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input().split(' ')
for i in range(N):
  A[i] = int(A[i])
cnt = 0
for i in range(N):
  if A[i]<0:
    cnt += 1
if cnt%2==0:
  rlt = 0
  for i in range(N):
    rlt += abs(A[i])
else:
  sml = 0
  for i in range(N-1):
    if abs(A[i])>abs(A[i+1]):
      sml = i+1
  rlt = 0
  for i in range(N):
      if i != sml:
        rlt += abs(A[i])
      else:
        rlt += -(abs(A[i]))
print(rlt)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))

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

a=np.array(a)
a2 = a
np.abs(a)
goukei=0

if mynas % 2 ==0:
    for j in range(n):
        goukei += a[j]
else:
    a2=np.sort(a)
    for k in range(n):
        goukei+=a[i]
    goukei-=a[0]*2

print(goukei)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
input = sys.stdin.readline

# bisect_left(lists, 3)
# bisect_right(lists, 3)

def main():
	N = int(input())
	A = input().split()
	A = [int(s) for s in A]

	ans = 0
	dels = 0
	naiCounts = 0
	lasts = -1
	for i, val in enumerate(A):
		if val < 0:
			lasts = i
			naiCounts += 1
		if val == 0:
			lasts = -1
			naiCounts = 0

	if naiCounts % 2 == 0 or naiCounts == 0:
		for i, val in enumerate(A):
			if val < 0:
				ans = ans + (val * -1)
			else:
				ans += val
		print(ans)
		sys.exit()

	tmp = -1
	for i, val in enumerate(A):
		if i < lasts:
			continue

		if tmp -1 or tmp > abs(val):
			dels = i
	
	#print(dels)
	for i, val in enumerate(A):
		if i == dels:
			#print(val)
			if val < 0:
				ans += val
			else:
				ans -= val
		else:
			if val < 0:
				ans = ans + (val * -1)
			else:
				ans += val


	print(ans)



def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
num = list(map(int,input().split()))
g = 0
for i in range(1,n):
    if i==n-1 and num[i-1]*-1<num[i]*-1 or i!=n-1 and num[i-1]*-1>num[i]*-1:
        num[i-1]*=-1
        num[i]*=-1
print(sum(num))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  A[i] = abs(A[i])
print(sum(A))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
from sys import stdin

readline = stdin.readline

_, *a = map(int, open(0).read().split())
res = 0
mi = 1000000000
rem = True
for v in a:
    if v < 0:
        rem = not rem
    b = abs(v)
    res += b
    mi = min(b, mi)
if rem:
    res -= mi*2
print(res)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl
import fractions
from functools import reduce
import copy
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


n = int(input())
su = 0

a = l()

co = 0
k = 0
a.sort()
f = 0
for i in range(n):
	if a[i] <= 0:
		co += 1
if co % 2 == 0:
	for i in range(n):
		su += abs(a[i])
	print(su)
else:
	for i in range(n):
		if f == 2:
			break
		if a[i] >= 0 and f == 0:
			kk = a[i-1]
			f = 1
		if a[i] >= 1:
			if abs(a[-1]) >= a[i]:
				k = a[i]*-2
			else:
				k = kk*2
			f = 2
		elif i == n-1:
			k = a[i]*2
	for i in range(n):
		su += abs(a[i])
	su += k
	print(su)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

m = sum(As)
for i in range(N-1):
	nl = As[0:i] + [-1*As[i]] + [-1*As[i+1]] + As[i+1:N]
	nls = sum(nl)
	if(m <= nls):
		m = nls
		As = nl

print(m)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))

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

a=np.array(a)
a2 = np.abs(a)
goukei=0

if mynas % 2 ==0:
    for j in range(n):
        goukei += a2[j]
else:
    a2=np.sort(a)
    for k in range(n):
        goukei+=a[i]
    goukei-=a[0]*2

print(goukei)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
ans=sum(a)
while 1:
    for i in range(n-1):
        print(*a)
        if a[i]+a[i+1]<-a[i]-a[i+1]:
            a[i]*=-1
            a[i+1]*=-1
        elif a[i]+a[i+1]==-a[i]-a[i+1] and a[i+1]>0:
            a[i]*=-1
            a[i+1]*=-1
    if sum(a)==ans: break
    ans=max(ans,sum(a))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A_=A.copy()
for i in range(N-1):
    if A[i]>=0:
        continue
    else:
        A[i]*=-1
        A[i+1]*=-1

    if A_[i]>0:
        continue
    else:
        A_[i]*=-1
        A_[i+1]*=-1

sA = sum(A)
sA_ = sum(A_)
if sA > sA_:
    print(sA)
else:
    print(sA_)

Submission status: Wrong Answer

Solution code:
n=int(input())
aa=list(map(int,input().split()))
aa.append(0)
aaa=tuple(aa)
a=list(aaa)
for i in range(n-1):
    if a[i]<0:
        a[i]=-1*a[i]
        a[i+1]=-1*a[i+1]
b=list(aaa)
for i in range(n,0,-1):
    if b[i]<0:
        b[i]=-1*b[i]
        b[i-1]=-1*b[i-1]

print(max(sum(a),sum(b)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


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

    for i in range(1, n):
        if a[i - 1] <= 0 and a[i] <= 0:
            a[i - 1] *= -1
            a[i] *= -1
        elif a[i - 1] <= 0 and a[i] >= 0:
            a[i - 1] *= -1
            a[i] *= -1

    print(sum(a))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

cnt = 0
for i in range(N):
    if A[i] <= 0:
        cnt += 1
    
ans = 0
if cnt % 2 == 0:
    for i in range(N):
        ans += abs(A[i])
else:
    for i in range(N - 2):
        ans += abs(A[i])
    if abs(A[-2]) > abs(A[-1]):
        ans += abs(A[-2])
        if A[-1] < 0:
            ans += A[-1]
        else:
            ans += - A[-1]
    else:
        ans += abs(A[-1])
        if A[-2] < 0:
            ans += A[-2]
        else:
            ans += - A[-2]
    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a_l = list(map(int, input().split()))

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


print(sum(a_l))

Submission status: Wrong Answer

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

sum = 0

for i in range(n - 1):
    if i != n - 2:
        if a[i] < 0:
            a[i + 1] = - a[i + 1]
            sum = sum - a[i]
        else:
            sum = sum + a[i]
    else:
        al = a[i] + a[i + 1]
        if al < 0:
            sum = sum - al
        else:
            sum = sum + al

print(sum)

Submission status: Wrong Answer

Solution code:
n=int(input())
ina=list(map(int,input().split()))
a=[]
flg=False
cnt=0

for i in range(n):
  tmp=ina[i]
  a.append(abs(tmp))
  if tmp<0:
    cnt+=1
    if flg==False:
      flg=True
      mi=abs(tmp)
  if flg and mi>abs(tmp):
    mi=abs(tmp)
if cnt%2==0:
  print(sum(a))
else:
  print(sum(a)-mi*2)

Submission status: Wrong Answer

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

i = 0
next_compute = True
sum_a = 0
while (i < N):
    # print(next_compute)
    if i == N - 1:
        if next_compute:
            sum_a += A[i]
        else:
            sum_a += (-A[i])
        break
    sum_a += abs(A[i])
    if 0 == A[i]:
        next_compute = True
    elif 0 <= A[i] and next_compute:
        # print(str(i) + ': a ' + str(A[i]))
        next_compute = True
    elif 0 <= A[i] and not next_compute:
        # print(str(i) + ': b ' + str(A[i]))
        next_compute = False
    elif A[i] < 0 and next_compute:
        # print(str(i) + ': c ' + str(A[i]))
        next_compute = False
    else:
        # print(str(i) + ': d ' + str(A[i]))
        next_compute = True
    i += 1

i = N - 1
prev_compute = True
sum_a_r = 0
while (0 <= i):
    if i == 0:
        if prev_compute:
            sum_a_r += A[i]
        else:
            sum_a_r += (-A[i])
        break
    sum_a_r += abs(A[i])
    if 0 == A[i]:
        prev_compute = True
    elif 0 <= A[i] and prev_compute:
        prev_compute = True
    elif 0 <= A[i] and not prev_compute:
        prev_compute = False
    elif A[i] < 0 and prev_compute:
        prev_compute = False
    else:
        prev_compute = True
    i -= 1

# print(sum_a)
# print(sum_a_r)
if sum_a < sum_a_r:
    print(sum_a_r)
else:
    print(sum_a)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


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

    for i in range(1, n):
        if a[i - 1] < 0 and a[i] < 0:
            a[i - 1] *= -1
            a[i] *= -1
        elif a[i - 1] < 0 and a[i] >= 0:
            a[i - 1] *= -1
            a[i] *= -1

    print(sum(a))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
total = 0
for i in range(n-1):
    if a[i]>0:
        total+=a[i]
    else:
        before = a[i]+a[i+1]
        after = a[i]*(-1) + a[i+1]*(-1)
        if before<=after:
            a[i] *= -1
            a[i + 1] *= -1
        # print('a:',a)
        total+=a[i]
total+=a[-1]
print(total)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
for i in range(0,N-1):
    if a[i] < 0:
        a[i] *= -1
        a[i+1] *= -1
print(sum(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
for i in range(N-1):
  if A[i] + A[i+1] < 0:
    A[i] = -A[i]
    A[i+1] = -A[i+1]
print(sum(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
last = 0
for i in range(n - 1):
    flag = False
    if i == n - 2:
        if last:
            if last <= 0:
                if a[i + 1] <= 0:
                    flag = True
                elif -last >= a[i + 1]:
                    flag = True
            else:
                if a[i + 1] <= 0 and -a[i + 1] >= last:
                    flag = True
            if flag:
                ans -= last
                ans -= a[i + 1]
            else:
                ans += last
                ans += a[i + 1]
        else:
            if a[i] <= 0:
                if a[i + 1] <= 0:
                    flag = True
                elif -a[i] >= a[i + 1]:
                    flag = True
            else:
                if a[i + 1] <= 0 and -a[i + 1] >= a[i]:
                    flag = True
            if flag:
                ans -= a[i]
                ans -= a[i + 1]
            else:
                ans += a[i]
                ans += a[i + 1]
    else:
        if last:
            if last <= 0:
                if a[i + 1] <= 0:
                    flag = True
                elif -last >= a[i + 1]:
                    flag = True
            if flag:
                ans -= last
                last = -a[i + 1]
            else:
                ans += last
                last = 0
        else:
            if a[i] <= 0:
                if a[i + 1] <= 0:
                    flag = True
                elif -a[i] >= a[i + 1]:
                    flag = True
            if flag:
                ans -= a[i]
                last = -a[i + 1]
            else:
                ans += a[i]
                last = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input().split(' ')
for i in range(N):
  A[i] = int(A[i])
cnt = 0
for i in range(N):
  if A[i]<0:
    cnt += 1
if cnt%2==0:
  rlt = 0
  for i in range(N):
    rlt += abs(A[i])
else:
  sml = 0
  for i in range(N-2):
    if abs(A[i])>abs(A[i+1]):
      sml = i+1
  if abs(A[sml])<abs(A[N-1]):
    rlt = 0
    for i in range(N):
      if i != sml:
        rlt += abs(A[i])
      else:
        rlt += -(abs(A[i]))
  else:
    rlt = 0
    for i in range(N-1):
    	rlt += abs(A[i])
    rlt += -(abs(A[N-1]))
print(rlt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
input = sys.stdin.readline

# bisect_left(lists, 3)
# bisect_right(lists, 3)

def main():
	N = int(input())
	A = input().split()
	A = [int(s) for s in A]

	ans = 0
	dels = 0
	naiCounts = 0
	lasts = -1
	for i, val in enumerate(A):
		if val < 0:
			lasts = i
			naiCounts += 1
		if val == 0:
			lasts = -1
			naiCounts = 0

	if naiCounts % 2 == 0 or naiCounts == 0:
		for i, val in enumerate(A):
			if val < 0:
				ans = ans + (val * -1)
			else:
				ans += val
		print(ans)
		sys.exit()

	tmp = -1
	for i, val in enumerate(A):
		if i < lasts:
			continue

		if tmp -1 or tmp > abs(val):
			dels = i
	
	print(dels)
	for i, val in enumerate(A):
		if i == dels:
			if val < 0:
				ans += val
			else:
				ans -= val
		else:
			if val < 0:
				ans = ans + (val * -1)
			else:
				ans += val


	print(ans)



def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
A=int(input())
B=[_ for _ in map(int,input().split())]
"マイナスの数を求める"
minus=0
for i in B:
  if i<=0:
    minus=+1
"マイナスの数が偶数の場合、絶対値Bを全部足す"
ans=0
if minus%2==0:
  for i in B:
    if i<=0:
      ans=+(-1)*i
    else:
      ans+=i
  print(ans)

else:
  S=0
  for i in range(A):
    B[i]=abs(B[i])
  for i in B:
    S+=i
  print(S-2*min(B))

Submission status: Wrong Answer

Solution code:
N = input()
A = map(int, raw_input().split())
B = []
flag = 2
flag2 = 0
k = 0
minabs = 0
for i in range(N):
	k = abs(A[i])
	B.append(k)
	if(k != 0 and (k < minabs or minabs == 0)):
		minabs = k
	if(i == N - 1):
		if(flag == 2 or A[i] == 0 or flag2 == 1):
			flag2 = 1
		elif((flag == 1 and A[i] < 0) or (flag == 0 and A[i] > 0)):
			flag2 = 1
		else:
			flag2 = 0
	else:
		if(flag == 2):
			if(A[i] > 0):
				flag = 0
			elif(A[i] == 0):
				flag2 = 1
			else:
				flag = 1
		if((A[i] > 0 and flag == 0) or (A[i] < 0 and flag == 1)):
			flag = 0
		elif((A[i] < 0 and flag == 0) or (A[i] > 0 and flag == 1)):
			flag = 1
		else:
			flag2 = 1
if(flag2 == 1):
	print(sum(B))
else:
	print(sum(B)- minabs * 2)

Submission status: Wrong Answer

Solution code:
n=int(input())
ina=list(map(int,input().split()))
a=[]
flg=False
cnt=0
mi=9999999999
for i in range(n):
  tmp=ina[i]
  a.append(abs(tmp))
  if tmp<0:
    cnt+=1
    if flg==False:
      flg=True
  if flg and mi>abs(tmp):
    mi=abs(tmp)
if cnt%2==0:
  print(sum(a))
else:
  print(sum(a)-mi*2)

Submission status: Wrong Answer

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

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

print(sum(A))

Submission status: Wrong Answer

Solution code:
A=int(input())
B=[_ for _ in map(int,input().split())]
"マイナスの数を求める"
minus=0
for i in B:
  if i<=0:
    minus=+1
"マイナスの数が偶数の場合、絶対値Bを全部足す"
ans=0
if minus%2==0:
  for i in B:
    if i<=0:
      ans=+(-1)*i
    else:
      ans+=i
    print(ans)

else:
  S=0
  for i in range(A):
    B[i]=abs(B[i])
  for i in B:
    S+=i
  print(S-2*min(B))

Submission status: Wrong Answer

Solution code:
import atexit
import io
import sys

buff = io.BytesIO()
sys.stdout = buff


@atexit.register
def write():
    sys.__stdout__.write(buff.getvalue())


n = input()
arr = map(int, raw_input().split())
dp = [[0, 0, 0, 0] for i in xrange(n)]
dp[0][0] = arr[0]
dp[0][1] = -int(1e18)
dp[0][2] = -arr[0]
dp[0][3] = -int(1e18)

for i in xrange(1,n):
	dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + arr[i]
	dp[i][1] = max(dp[i-1][2], dp[i-1][3]) - arr[i]
	dp[i][2] = max(dp[i-1][0], dp[i-1][1]) - arr[i]
	dp[i][3] = dp[i-1][2] + arr[i]

dp[n-1][3] = int(-1e18)
dp[n-1][2] = int(-1e18)
print max(dp[n-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N):
    if A[i] <= 0:
        count += 1
ans = 0
if count%2 == 0:
    for i in range(N):
        ans += max(A[i],-A[i])
else:
    tmp = -1000000000
    c = 0
    for i in range(N):
        if tmp < min(A[i],-A[i]) < 0:
            tmp = min(A[i],-A[i])
            c = i
    for i in range(N):
        if i != c:
            ans += max(A[i],-A[i])
        else:
            ans += tmp
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.append(0)
for i in range(n-1):
    if a[i]<0:
        a[i]=-1*a[i]
        a[i+1]=-1*a[i+1]

print(sum(a))

Submission status: Wrong Answer

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


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


if N == 2:
    print(max(A[0], A[1]))
    quit()
if N == 3:
    print(max(gcd(A[0], A[1]), gcd(A[0], A[2]), gcd(A[1], A[2])))
    quit()

ans0 = A[0]
ans1 = A[-1]
for i in range(N//2-1):
    ans0 = min(gcd(A[i], A[i+1]), ans0)
for i in range(N//2, N-1):
    ans1 = min(gcd(A[i], A[i+1]), ans1)
ans = max(ans0, ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
As = [int(i) for i in input().split()]
absl = [abs(a) for a in As]

neg = sum(1 for a in As if a < 0)

# print(neg)

if neg // 2 == 0:
    print(sum(absl))
else:
    print(sum(absl) - min(absl) * 2)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
f=0
m=0
for i in range(2):
  if len(a[i::2])%2:
    s=sorted([abs(c)for c in a[i::2]])[::-1]
    f+=sum(s[:-1])
    m+=s[-1]
  else:
    f+=sum([abs(c)for c in a[i::2]])
print(f-m)

Submission status: Wrong Answer

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

for i in range(n-2):
    if a[i] >= 0:
        continue
    else:
        a[i] *= -1
        a[i+1] *= -1
if (a[n-2] <= 0 and a[n-1] <= 0):
    a[n-2] *= -1
    a[n-1] *= -1
elif (a[n-2] <= 0 <= a[n-1] and abs(a[n-2]) > a[n-1]):
    a[n-2] *= -1
    a[n-1] *= -1
elif (a[n-2] >= 0 >= a[n-1] and a[n-2] < abs(a[n-1])):
    a[n-2] *= -1
    a[n-1] *= -1
print(sum(a))

Submission status: Wrong Answer

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

for i in range(len(data) - 1):
    if data[i] < 0 and -1 * (data[i] + data[i + 1]) >= (data[i] + data[i + 1]):
        data[i] = -1 * data[i]
        data[i + 1] = -1 * data[i + 1]

print(sum(data))

Submission status: Wrong Answer

Solution code:
N = input()
A = map(int, raw_input().split())
B = []
flag = 2
flag2 = 0
k = 0
minabs = 0
for i in range(N):
	k = abs(A[i])
	B.append(k)
	if(k != 0 and (k < minabs or minabs == 0)):
		minabs = k
	if(i == N - 1):
		if(flag == 2 or A[i] == 0 or flag2 == 1):
			flag2 = 1
		elif((flag == 1 and A[i] < 0) or (flag == 0 and A[i] > 0)):
			flag2 = 1
		else:
			flag2 = 0
	else:
		if(flag == 2):
			if(A[i] > 0):
				flag = 0
			elif(A[i] == 0):
				flag2 = 1
			else:
				flag = 1
		if((A[i] > 0 and flag == 0) or (A[i] < 0 and flag == 1)):
			flag = 0
		elif((A[i] < 0 and flag == 0) or (A[i] > 0 and flag == 1)):
			flag = 1
		else:
			flag2 = 1
if(flag2 == 1):
	print(sum(B))
else:
	print(sum(B)- minabs * 2)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input().split(' ')
for i in range(N):
  A[i] = int(A[i])
cnt = 0
for i in range(N):
  if A[i]<0:
    cnt += 1
if cnt%2==0:
  rlt = 0
  for i in range(N):
    rlt += abs(A[i])
else:
  sml = 0
  for i in range(N-2):
    if abs(A[i])>abs(A[i+1]):
      sml = i+1
  if abs(A[sml])<abs(A[N-1]):
    rlt = 0
    for i in range(N):
      if i != sml:
        rlt += abs(A[i])
      else:
        rlt += A[i]
  else:
    rlt = 0
    for i in range(N-1):
    	rlt += abs(A[i])
    rlt += -(A[N-1])
print(rlt)

Submission status: Wrong Answer

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

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

b = []
for j in range(len(a)):
    b.append(abs(a[j]))

if cnt % 2 != 0:
        b.append(2*min(b))

print(sum(b))

Submission status: Wrong Answer

Solution code:
read_ints = lambda : map(int, raw_input().strip().split())

n = input()
a = read_ints()

neg = 0
mn = float('inf')
s = 0
for num in a:
    mn = min(mn, abs(num))
    s += abs(num)
    if num < 0: neg += 1

if neg & 1:
    print s - mn
else:
    print s

Submission status: Wrong Answer

Solution code:
n = int(input())
num = list(map(int,input().split()))
g = 0
for i in range(1,n):
    if num[i-1]<0 or i==n-1 and abs(num[i])>abs(num[i-1]):
        num[i-1]*=-1
        num[i]*=-1
print(sum(num))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

for i in range(N-1):
    if A_list[i] < 0 and i != N-2:
        A_list[i] = A_list[i] * -1
        A_list[i+1] = A_list[i+1] * -1
    elif (A_list[i] + A_list[i-1]) < 0:
        A_list[i] = A_list[i] * -1
        A_list[i+1] = A_list[i+1] * -1
        
print(sum(A_list))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
print(sum(a)-2*a[-1])