Problem:


Score : 400 points

Problem Statement

You are given N integers; the i-th of them is A_i.
Find the maximum possible sum of the absolute differences between the adjacent elements after arranging these integers in a row in any order you like.

Constraints

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the maximum possible sum of the absolute differences between the adjacent elements after arranging the given integers in a row in any order you like.

Sample Input 1

5
6
8
1
2
3

Sample Output 1

21

When the integers are arranged as 3,8,1,6,2, the sum of the absolute differences between the adjacent elements is |3 - 8| + |8 - 1| + |1 - 6| + |6 - 2| = 21. This is the maximum possible sum.

Sample Input 2

6
3
1
4
1
5
9

Sample Output 2

25

Sample Input 3

3
5
5
1

Sample Output 3

8



Sample input:
5
6
8
1
2
3


Sample output:
21

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()

d_A = deque(A)
d = deque()
d.append(d_A.popleft())
for i in range(N-1):
    target = d_A.popleft() if i % 2 != 0 else d_A.pop()
    right = abs(d[-1] - target)
    left = abs(d[0] - target)
    if right >= left:
        d.append(target)
    else:
        d.appendleft(target)
ans = 0
for i in range(1,N):
    ans += abs(d[i]-d[i-1])

d_A = deque(A)
d = deque()
d.append(d_A.pop())
for i in range(N-1):
    target = d_A.popleft() if i % 2 == 0 else d_A.pop()
    right = abs(d[-1] - target)
    left = abs(d[0] - target)
    if right > left:
        d.append(target)
    else:
        d.appendleft(target)
ans2 = 0
for i in range(1,N):
    ans2 += abs(d[i]-d[i-1])
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
d_A = deque(A)
d = deque()
d.append(d_A.popleft())
for i in range(N-1):
    target = d_A.popleft() if i % 2 != 0 else d_A.pop()
    right = abs(d[-1] - target)
    left = abs(d[0] - target)
    if right >= left:
        d.append(target)
    else:
        d.appendleft(target)
ans = 0
for i in range(1,N):
    ans += abs(d[i]-d[i-1])

d_A = deque(A)
d = deque()
d.append(d_A.pop())
for i in range(N-1):
    target = d_A.popleft() if i % 2 == 0 else d_A.pop()
    right = abs(d[-1] - target)
    left = abs(d[0] - target)
    if right >= left:
        d.append(target)
    else:
        d.appendleft(target)
ans2 = 0
for i in range(1,N):
    ans2 += abs(d[i]-d[i-1])
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
d_A = deque(A)
d = deque()
d.append(d_A.popleft())
for i in range(N-1):
    target = d_A.popleft() if i % 2 != 0 else d_A.pop()
    right = abs(d[-1] - target)
    left = abs(d[0] - target)
    if right > left:
        d.append(target)
    else:
        d.appendleft(target)
ans = 0
for i in range(1,N):
    ans += abs(d[i]-d[i-1])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
d_A = deque(A)
d = deque()
d.append(d_A.popleft())
for i in range(N-1):
    target = d_A.popleft() if i % 2 != 0 else d_A.pop()
    right = abs(d[-1] - target)
    left = abs(d[0]-target)
    if right >= left:
        d.append(target)
    else:
        d.appendleft(target)
ans = 0
for i in range(1,N):
    ans += abs(d[i]-d[i-1])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = []
for _ in range(n):
    dat.append(int(input()))
dat.sort()
# 1 2 3 4 5
# 1 2 3 4
if n == 2:
    print(abs(dat[0] - dat[1]))
if n & 1 == 0:
    x1 = n // 2
    x2 = x1 - 1
    res = 0
    for i in range(n):
        if i < x2:
            res += (dat[i]) * -2
            continue
        if i == x2:
            res += (dat[i]) * -1
            continue
        if i == x1:
            res += (dat[i])
            continue
        if i > x1:
            res += (dat[i]) * 2
            continue
    print(res)
else:
    xc = n // 2
    xl = xc - 1
    xr = xc + 1

    res = 0
    for i in range(n):
        if i < xl:
            res += (dat[i]) * -2
            continue
        if i == xl:
            res += (dat[i]) * -1
            continue
        if i == xc:
            res += (dat[i]) * -1
            continue
        if i > xc:
            res += (dat[i]) * 2
            continue

    res2 = 0
    for i in range(n):
        if i < xc:
            res2 += (dat[i]) * -2
            continue
        if i == xc:
            res2 += (dat[i]) * 1
            continue
        if i == xr:
            res2 += (dat[i]) * 1
            continue
        if i > xr:
            res2 += (dat[i]) * 2
            continue

    print(max(res, res2))

Submission status: Wrong Answer

Solution code:
n=int(input())
L=[0]*n
for i in range(n):
  L[i]=int(input())
L.sort()
L.reverse()
ans=0
for i in range(n):
  if i<=(n//2)-1:
    ans+=2*L[i]
  else:
    ans-=2*L[i]
if(n%2==0):
  ans-=L[n//2-1]-L[n//2]
else:
  ans+=L[n//2]+L[n//2+1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

N = i()
A = []
for j in range(N):
    a = i()
    A.append(a)

A.sort()
b = N // 2 -1
if N % 2 == 0:
    for i in range(b):
        ans += 2*A[N-1-i]-2*A[i]

    ans += A[b+1]-A[b]
else:
    for i in range(b):
        ans += 2*A[N-1-i]-2*A[i]

    ans += 2*A[N-1-b]-A[b+1]-A[b]




print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,gcd
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')

#Pythonを用いる場合
#numpy 1.18.0, scipy 1.4.1, scikit-learn 0.22, numba 0.47.0, networkx 2.4
 
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=deque(list(sorted([ii() for _ in range(n)])))

mat=deque([])

for i in range(n):
    if i%4==0:
        p=arr.popleft()
        mat.append(p)
    elif i%4==1:
        p=arr.pop()
        mat.appendleft(p)
    elif i%4==2:
        p=arr.pop()
        mat.append(p)
    else:
        p=arr.popleft()
        mat.appendleft(p)

ans=0
chk=list(mat)
for i in range(n-1):
    ans+=abs(chk[i]-chk[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    D = deque(A)
    d = D.popleft()
    ans = deque([d])
    cnt = 0
    while D:
        if cnt % 2 == 0:
            i = D.pop()
            ans.appendleft(i)
            if D:
                j = D.pop()
                ans.append(j)
        else:
            i = D.popleft()
            ans.appendleft(i)
            if D:
                j = D.popleft()
                ans.append(j)
        cnt += 1

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

    print(tmp)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(input()) for _ in range(n)])

if n == 2:
    print(a[1] - a[0])
elif n == 3:
    print(a[2] + a[1] - 2 * a[0])
elif n % 2 == 0:
    ans1 = 2 * (sum(a[n // 2:]) - sum(a[:n // 2]))
    ans1 += a[n // 2 -1] - a[n // 2]
    print(ans1)
elif n % 2 == 1:
    ans = 2 * (sum(a[n // 2 + 1:]) - sum(a[:n // 2 + 1]))
    print(ans + a[n // 2] + a[n // 2 - 1])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(input()) for _ in range(n)])

if n == 2:
    print(a[1] - a[0])
elif n == 3:
    print(a[2] + a[1] - 2 * a[0])
elif n % 2 == 0:
    ans1 = 2 * (sum(a[n // 2:]) - sum(a[:n // 2]))
    ans1 += a[n // 2] - a[n // 2 + 1]
    print(ans1)
elif n % 2 == 1:
    ans = 2 * (sum(a[n // 2 + 1:]) - sum(a[:n // 2 + 1]))
    print(ans + a[n // 2] + a[n // 2 - 1])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(input()) for _ in range(n)])

if n == 2:
    print(a[1] - a[0])
elif n == 3:
    print(a[2] + a[1] - 2 * a[0])
elif n % 2 == 0:
    ans1 = 2 * (sum(a[n // 2:]) - sum(a[:n // 2]))
    ans1 += a[n // 2] - a[n // 2 + 1]
    ans2 = 2 * (sum(a[n // 2 - 1:]) - sum(a[:n // 2 - 1]))
    ans2 += a[n // 2 - 1] + a[n // 2]
    print(max(ans1, ans2))
elif n % 2 == 1:
    ans = 2 * (sum(a[n // 2 + 1:]) - sum(a[:n // 2 + 1]))
    print(ans + a[n // 2] + a[n // 2 - 1])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(input()) for _ in range(n)])

if n == 2:
    print(a[1] - a[0])
elif n == 3:
    print(a[2] + a[1] - 2 * a[0])
elif n % 2 == 0:
    ans = 2 * (sum(a[n // 2:]) - sum(a[:n // 2]))
    print(ans + a[n // 2 - 1] - a[n // 2])
elif n % 2 == 1:
    ans = 2 * (sum(a[n // 2 + 1:]) - sum(a[:n // 2 + 1]))
    print(ans + a[n // 2] + a[n // 2 - 1])

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

a.sort()
# print(a)
d=deque([a[0]])
for i in range(1,n):
    # print(-i//2)
    if i%2==1:
        tmp=a[-i//2]
    else:
        tmp=a[i//2]
    if abs(d[0]-tmp)>abs(d[-1]-tmp):
        d.appendleft(tmp)
    else:
        d.append(tmp)

ans=0
for i in range(1,n):
    ans+=abs(d[i]-d[i-1])
# print(ans)

d=deque([a[-1]])
for i in range(n-1):
    # print(-i//2)
    if i%2==1:
        tmp=a[-i//2-1]
    else:
        tmp=a[i//2]
    if abs(d[0]-tmp)>abs(d[-1]-tmp):
        d.appendleft(tmp)
    else:
        d.append(tmp)
    # print(tmp)
ans1=0
for i in range(1,n):
    ans1+=abs(d[i]-d[i-1])
print(max(ans1,ans))

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

a.sort()
# print(a)
d=deque([a[0]])
for i in range(1,n):
    # print(-i//2)
    if i%2==1:
        tmp=a[-i//2]
    else:
        tmp=a[i//2]
    if abs(d[0]-tmp)>abs(d[-1]-tmp):
        d.appendleft(tmp)
    else:
        d.append(tmp)

ans=0
for i in range(1,n):
    ans+=abs(d[i]-d[i-1])
print(ans)

Submission status: Wrong Answer

Solution code:
N,*a=map(int,open(0));n=N//2-1;a.sort();print(N%2and 2*sum(a[n+2:])-2*sum(a[:n])+a[n+1]-a[n]-(min(a[n]+a[n+2],2*a[n+1])or 0))

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
A = [INT() for _ in range(N)]

A.sort()

a = A[:-(-N//2)]
b = A[::-1][:N//2]

q = deque([a[0], b[0]])

for i in range(1, len(b)):
	if abs(a[i]-q[-1]) > abs(a[i]-q[0]):
		q.append(a[i])
		q.appendleft(b[i])
	elif abs(a[i]-q[-1]) < abs(a[i]-q[0]):
		q.appendleft(a[i])
		q.append(b[i])
	else:
		if abs(b[i]-q[-1]) > abs(b[i]-q[0]):
			q.append(b[i])
			q.appendleft(a[i])
		else:
			q.appendleft(b[i])
			q.append(a[i])

if len(a) > len(b):
	if abs(a[-1]-q[-1]) > abs(a[-1]-q[0]):
		q.append(a[-1])
	elif abs(a[-1]-q[-1]) < abs(a[-1]-q[0]):
		q.appendleft(a[-1])

#print(q)
print(sum([abs(q[i]-q[i-1]) for i in range(1, len(q))]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
a.sort()

l =a[0]
r = a[0]
count = 0
ans = 0
for i in range(n):
    if count >= n:
        break
    x = abs(a[i]-l)
    y = abs(a[i]-r)
    if x >= y:
        ans += x
        l = a[i]
    else:
        ans += y
        r = a[i]
    count += 1
    if count >= n:
        break
    x = abs(a[-i-1]-l)
    y = abs(a[-i-1]-r)
    if x >= y:
        ans += x
        l = a[-i-1]
    else:
        ans += y
        r = a[-i-1]
    count += 1
l =a[-1]
r = a[-1]
count = 0
ans2 = 0
for i in range(n):
    if count >= n:
        break
    x = abs(a[-i-1]-l)
    y = abs(a[-i-1]-r)
    if x >= y:
        ans2 += x
        l = a[-i-1]
    else:
        ans2 += y
        r = a[-i-1]
    count += 1
    if count >= n:
        break
    x = abs(a[i]-l)
    y = abs(a[i]-r)
    if x >= y:
        ans2 += x
        l = a[i]
    else:
        ans2 += y
        r = a[i]
    count += 1
    
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
As = sorted([int(input()) for i in range(n)])
q = deque(As[1:])
ans = 0
cnt = 1
# 初期化
p1 = As[0]
p2 = As[0]
flg = False
while True:
    if len(q) == 0: break
    if flg:
        n1 = q.popleft()
    else:
        n1 = q.pop()
    ans += abs(p1-n1)
    p1 = n1

    if len(q) == 0: break
    if flg:
        n2 = q.popleft()
    else:
        n2 = q.pop()
    ans += abs(p2-n2)
    p2 = n2

    flg = not flg

print(ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = ILs(N)
A.sort()

if N == 3:
  a,b,c = A
  print(max(abs(a-c)+abs(a-b),abs(a-c)+abs(c-b)))
  exit()

if N%2:
  U = A[-(-N//2):]
  D = A[:-(-N//2)]
  print((sum(U)-sum(D))*2+D[-1]+D[-2])
else:
  U = A[N//2:]
  D = A[:N//2]
  print((sum(U)-sum(D))*2-U[0]+D[-1])

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = ILs(N)
A.sort()

prev = (A[0],A[0])

ans = 0
flag = 1
q = deque(A[1:])
while q:
  c,d = prev
  if flag == 0:
    a = q.popleft()
  else:
    a = q.pop()
  if abs(a-c) >= abs(a-d):
    ans += abs(a-c)
    prev = (a,d)
  else:
    ans += abs(a-d)
    prev = (a,c)
  flag = 1-flag
print(ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = ILs(N)
A.sort()


ans = 0

if N%2:
  prev = (A[0],A[0])
  A = A[1:]
else:
  prev = (A[0],A[1])
  ans += abs(A[0]-A[-1])+abs(A[1]-A[-1])
  A = A[2:-1]
q = deque(A)

flag = 1

while len(q)>1:
  c,d = prev
  if flag == 0:
    a = q.popleft()
    b = q.popleft()
  else:
    a = q.pop()
    b = q.pop()
  ans += max(abs(a-c)+abs(b-d),abs(a-d)+abs(b-c))
  prev = (a,b)
  flag = 1-flag
  
if q:
  a = q.popleft()
  c,d = prev
  ans += max(abs(a-c),abs(a-d))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
a.sort()
d = deque(a)
ans = deque([d.popleft()])
cur = 0
while d:
    if cur%2 == 0:
        ans.appendleft(d.pop())
        if len(d) != 0:
            ans.append(d.pop())
        cur += 1
    else:
        ans.append(d.popleft())
        if len(d) != 0:
            ans.appendleft(d.popleft())
        cur += 1
p = 0
for x, y in zip(list(ans), list(ans)[1:]):
    p += abs(x-y)
print(p)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
a.sort()
d = deque(a)
ans = deque([d.popleft()])
cur = 0
while d:
    if cur%2 == 0:
        ans.appendleft(d.pop())
        if len(d) != 0:
            ans.append(d.pop())
        cur += 1
    else:
        ans.appendleft(d.popleft())
        if len(d) != 0:
            ans.append(d.popleft())
        cur += 1
p = 0
for x, y in zip(list(ans), list(ans)[1:]):
    p += abs(x-y)
print(p)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
a.sort()
d = deque(a)
ans = deque([d.popleft()])
cur = 0
while d:
    if cur%2 == 0:
        ans.appendleft(d.pop())
        if len(d) != 0:
            ans.append(d.pop())
    else:
        ans.appendleft(d.popleft())
        if len(d) != 0:
            ans.append(d.popleft())
p = 0
for x, y in zip(list(ans), list(ans)[1:]):
    p += abs(x-y)
print(p)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    from collections import deque
    
    N=I()
    A2=[0]*N
    for i in range(N):
        A2[i]=I()
        
    A2.sort(reverse=True)
    
    A=deque()
    for i in range(N):
        A.append(A2[i])
    
    
    ans=0
    L=[0]*(2*N+1)
    L[N]=A.pop()
    l=N-1
    r=N+1
    
    for i in range(N-1):
        if i%4==0:
            a=A.popleft()
            L[l]=a
            ans+=abs(L[l]-L[l+1])
            l-=1
        elif i%4==1:
            a=A.popleft()
            L[r]=a
            ans+=abs(L[r]-L[r-1])
            r+=1
        elif i%4==2:
            a=A.pop()
            L[l]=a
            ans+=abs(L[l]-L[l+1])
            l-=1
        else:
            a=A.pop()
            L[r]=a
            ans+=abs(L[r]-L[r-1])
            r+=1
    print(ans)
            
            
            
        
    
    
    

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []

for i in range(n):
    num = int(input())
    a.append(num)

a.sort()

if n % 2 == 0:
    b = a[0:n//2]
    c = a[n//2:]
    min_top = b.pop(-1)
    max_top = c.pop(0)
    ans = max_top + 2 * sum(c) - min_top - 2 * sum(b)
    print(b, c, min_top, max_top)

else:
    # c が一個多い
    b = a[0:n//2]
    c = a[n//2:]
    max_top1 = c.pop(0)
    max_top2 = c.pop(0)
    # e が一個多い
    d = a[0:n//2+1]
    e = a[n//2+1:]
    min_top1 = d.pop(-1)
    min_top2 = d.pop(-1)
    ans1 = max_top1 + max_top2 + 2 * sum(c) - 2 * sum(b)
    ans2 = 2 * sum(e) - 2 * sum(d) - min_top1 - min_top2
    ans = max(ans1, ans2)

print(ans)