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

Solution (Python):
def main():
    from itertools import cycle

    n = int(input())
    *a, = sorted(int(input()) for _ in range(n))

    half = n // 2
    h = reversed(a[:half])
    t = reversed(a[-half:])

    if n % 2 == 0:
        lis = []
        for e, o in zip(h, t):
            lis.append(e)
            lis.append(o)

        it = iter(lis)
        p = next(it)

        ret = 0
        for x in it:
            ret += abs(p - x)
            p = x

        print(ret)

    else:
        
        
        
        
        
        
        

        xs, ys = a[:-half], a[-half:]

        x = xs.pop()
        xs = [x] + xs

        cycl = cycle((xs, ys))

        p = next(cycl).pop()

        ret = 0
        for _ in range(n - 1):
            e = next(cycl).pop()
            ret += abs(p - e)
            p = e

        zs, ws = a[:half], a[half:]

        w, *ws = ws
        ws.append(w)

        cycl = cycle((ws, zs))

        p = next(cycl).pop()

        buf = 0
        for _ in range(n - 1):
            e = next(cycl).pop()
            buf += abs(p - e)
            p = e

        ret = max(ret, buf)

        print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
B = sorted(A)
H = N//2
if N%2==0:
    ans = -2*sum(B[:H-1]) -B[H-1] +B[H] +2*sum(B[H+1:])
    print(ans)
else:
    ans1 = -2*sum(B[:H-1]) -B[H-1] -B[H] +2*sum(B[H+1:])
    ans2 = -2*sum(B[:H]) +B[H] + B[H+1] +2*sum(B[H+2:])
    print(max(ans1, ans2))

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = [0] * 2 ;count = 0 ;pro = 1

n=int(input())
A=[int(input()) for i in range(n)]
A.sort()


tmp = 0;k=0
k+=n//2-1; tmp += -2*sum(A[:k])
tmp += -1*A[k]; k += 1
tmp += (-1)**n*A[k]; k += 1
tmp += 2 * sum(A[k:])
ans[0] = tmp


tmp = 0;k=0
k+=n//2-1+(n%2); tmp += -2*sum(A[:k])

tmp += (-1)**(n+1)*A[k]; k += 1
tmp += A[k]; k += 1
tmp += 2 * sum(A[k:])
ans[1] = tmp


print(max(ans))

Solution (Python):

from collections import deque
n=int(input())
a=[int(input()) for i in range(n)]
a.sort(reverse=True)
b=deque()
for i in range(n):
    t=0
    if i==n-1:
        t=a.pop(0)
        if abs(t-b[0])>=abs(t-b[-1]):
            b.appendleft(t)
        elif abs(t-b[0])<abs(t-b[-1]):
            b.append(t)
        break
    if i%2==0:
        if i==0:
            t=a.pop(0)
            b.append(t)
            continue
        if b[0]>=b[-1]:
            t=a.pop(0)
            b.append(t)
        elif b[0]<b[-1]:
            t=a.pop(0)
            b.appendleft(t)
    else:
        if i==1:
            t=a.pop(-1)
            b.append(t)
            continue
        if b[0]>=b[-1]:
            t=a.pop(-1)
            b.appendleft(t)
        elif b[0]<b[-1]:
            t=a.pop(-1)
            b.append(t)
ans=0
for i in range(n-1):
    ans+=abs(b[i+1]-b[i])
print(ans)

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

def main():
    N = int(input())
    A = [0] * N
    for i in range(N):
        A[i] = int(input())
    A.sort()

    tmp = N // 2
    if N % 2 == 1:
        L, M, R = A[:tmp], A[tmp], A[tmp+1:]
        
        print((sum(R) - sum(L)) * 2 + max(L[-1] - M, M - R[0]))
    else:
        L, R = A[:tmp], A[tmp:]
        """
        L[-1], R[0]は、第1項で
        それぞれ1回多く計算されているため、
        (L[-1] - R[0])としている
        """
        print((sum(R) - sum(L)) * 2 + (L[-1] - R[0]))

if __name__ == "__main__":
    main()

Solution (Python):
N, *A = map(int, open(0))
 
A.sort()
 
if N % 2 == 1:
    L, M, R = A[: N//2], A[N//2], A[N//2+1:]
    print((sum(R) - sum(L)) * 2 + max(- M + L[-1], M - R[0]))
else:
    L, R = A[:N // 2], A[N // 2:]
    print((sum(R) - sum(L)) * 2 - R[0] + L[-1])

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


def solve(N, A, fromR=True):
    res = 0
    L, R = None, None

    while A:
        fromR = 1 - fromR

        if L is None:
            L = A.pop() if fromR else A.popleft()
            R = L
            continue

        if len(A) > 1:
            if fromR:
                x = A.pop()
                y = A.pop()
            else:
                x = A.popleft()
                y = A.popleft()
            res += abs((R + L) - (x + y))
            R, L = x, y
            continue

        if len(A) == 1:
            x = A.pop()
            res += max(abs(R - x), abs(L - x))
            continue

    return res


if __name__ == "__main__":
    N = int(input())
    A = sorted([int(input()) for _ in range(N)])
    B = deque(A[::])
    A = deque(A)
    

    ans1 = solve(N, A, 0)
    ans2 = solve(N, B, 1)
    ans = max(ans1, ans2)
    print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
front = a[n - 1]
back = a[n - 1]
i = 0
j = n - 2
ans = 0
while i <= j:
    diff1 = abs(front - a[i])
    diff2 = abs(back - a[i])
    diff3 = abs(front - a[j])
    diff4 = abs(back - a[j])
    mx = max(diff1, diff2, diff3, diff4)
    ans += mx
    if mx == diff1:
        front = a[i]
        i += 1
    elif mx == diff2:
        back = a[i]
        i += 1
    elif mx == diff3:
        front = a[j]
        j -= 1
    else:
        back = a[j]
        j -= 1
print(ans)

Solution (Python):
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

A = sorted(A)

if N%2==0:
    l = A[:N//2]
    u = A[N//2:]
    ans = sum(u)*2-u[0] - (sum(l)*2-l[-1])
else:
    m = A[N//2]
    l = A[:N//2]
    u = A[N//2+1:]
    ans = max(sum(u)*2 - sum(l)*2 - m + l[-1], sum(u)*2 - sum(l)*2 + m - u[0])

print(ans)

Solution (Python):
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    A.sort()
    le, ri = A[-1], A[-1]
    
    from collections import deque
    A = deque(A[:N-1])
    ans = 0
    for i in range(N-1):
        cur = [abs(A[0] - le), abs(A[-1] - ri),
               abs(A[-1] - le), abs(A[0] - ri)]
        
        if max(cur) == cur[0]:
            c = A.popleft()
            ans += abs(c - le)
            le = c
        elif max(cur) == cur[1]:
            c = A.pop()
            ans += abs(c - ri)
            ri = c
        elif max(cur) == cur[2]:
            c = A.pop()
            ans += abs(c - le)
            le = c
        else:
            c = A.popleft()
            ans += abs(c - ri)
            ri = c
    print(ans)


if __name__ == '__main__':
    main()

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

A.sort()
q = deque([A[0]])
i = 1
j = N-1
while i <= j:
    temp = max(abs(A[i]-q[0]), abs(A[j]-q[0]), abs(A[i]-q[-1]), abs(A[j]-q[-1]))
    if temp == abs(A[i]-q[0]):
        q.appendleft(A[i])
        i += 1
    elif temp == abs(A[j]-q[0]):
        q.appendleft(A[j])
        j -= 1
    elif temp == abs(A[i]-q[-1]):
        q.append(A[i])
        i += 1
    else:
        q.append(A[j])
        j -= 1
L = list(q)
ans = 0
for i in range(N-1):
    ans += abs(L[i+1]-L[i])
print(ans)

Solution (Python):
N = int(input())
A = sorted([int(input()) for i in range(N)])
Ami = A[:N//2]
Ama = A[N//2:][::-1]
Ami2 = A[:(N+1)//2]
Ama2 = A[(N+1)//2:][::-1]

if N%2 == 1:
    ans = -2*sum(Ami)
    ans += 2*sum(Ama[:-2]) + Ama[-1]+Ama[-2]
    ans2 = -2*sum(Ami2[:-2]) - Ami2[-1]-Ami2[-2]
    ans2 += 2*sum(Ama2)
    print(max(ans2,ans))
else:
    ans = -2*sum(Ami[:-1]) - Ami[-1]
    ans += 2*sum(Ama[:-1]) + Ama[-1]
    print(ans)

Solution (Python):
n=int(input())
a=sorted([int(input()) for i in range(n)])
b=[a[i] for i in range(n-1,-1,-1)]
c=[abs(a[i//2]-b[i//2]) if i%2==0 else abs(b[i//2]-a[i//2+1]) for i in range(n-1)]
c.append(abs(b[(n-1)//2]-a[0]))
d=[abs(b[i//2]-a[i//2]) if i%2==0 else abs(a[i//2]-b[i//2+1]) for i in range(n-1)]
d.append(abs(a[(n-1)//2]-b[0]))
print(max(sum(c)-min(c),sum(d)-min(d)))

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]

A.sort()
a1, b1 = A[:N//2], sorted(A[N//2:], reverse=True)
a2, b2 = A[:N//2+1], sorted(A[N//2+1:], reverse=True)

cand1 = 2 * sum(b1[:len(a1) - 1]) + sum(b1[len(a1) - 1:]) - (2 * sum(a1[:len(b1) - 1]) + sum(a1[len(b1) - 1:]))
cand2 = 2 * sum(b2[:len(a2) - 1]) + sum(b2[len(a2) - 1:]) - (2 * sum(a2[:len(b2) - 1]) + sum(a2[len(b2) - 1:]))
print(max(cand1, cand2))

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

    N = int(input())
    A = [0] * N
    for i in range(N):
        A[i] = int(input())

    A.sort()
    i = 0
    j = N-1
    ans = A[j] - A[i]
    while j - i > 2:
        ans += A[j] - A[i+1] + A[j-1] - A[i]
        i += 1
        j -= 1
    if j - i == 2:
        ans += max(A[i+1] - A[i], A[i+2] - A[i+1])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
n = int(stdin.readline().rstrip())
li = [int(stdin.readline().rstrip()) for _ in range(n)]
li.sort()
if n%2 == 1:
    mid = li[n//2]
    mae = li[:n//2]
    ushiro = li[n//2+1:]
    sono1 = -mid - mae[-1]
    sono1 += sum(ushiro)*2-sum(mae[:-1])*2
    sono2 = mid + ushiro[0]
    sono2 += sum(ushiro[1:])*2-sum(mae)*2
    print(max(sono1,sono2))
else:
    mae = li[:n//2]
    ushiro = li[n//2:]
    sono3 = -mae[-1] + ushiro[0]
    sono3 += sum(ushiro[1:])*2-sum(mae[:-1])*2
    print(sono3)

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]

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

if N % 2 == 1:
    ans += max(abs(right - A[N // 2]), abs(left - A[N // 2]))

print(ans)

Solution (Python):
n=int(input())
a=[int(input())for _ in range(n)]
if n==2:print(abs(a[0]-a[1]));exit()
f=[-1]
for i in range(1,n-1-(n%2==0)):
  if i%2:f.append(2)
  else:f.append(-2)
if n%2:f+=[-1]
else:f+=[-2,1]
b=[]
c=[]
for i in f:
  b.append(i)
  c.append(-i)
b.sort()
c.sort()
sb=sc=0
a.sort()
for i in range(n):
  sb+=a[i]*b[i]
  sc+=a[i]*c[i]
print(max(sb,sc))

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()

if N % 2 == 0:
    s = N//2
    d = -2 * sum(A[:s]) + A[s-1] - A[s] + 2 * sum(A[s:])
else:
    s = N//2
    d1 = -2 * sum(A[:s]) - A[s] - A[s+1] + 2 * sum(A[s:])
    s += 1
    d2 = -2 * sum(A[:s]) + A[s-2] + A[s-1] + 2 * sum(A[s:])
    d = max(d1, d2)

print(d)

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]

A.sort()

l,r = A[0],A[0]
cnt = 1
l_cnt = cnt
r_cnt = 1
ans1 = 0
while True:
    ans1 += abs(l-A[-r_cnt])
    l = A[-r_cnt]
    cnt += 1
    r_cnt += 1
    if cnt == N:
        break

    ans1 += abs(r-A[-r_cnt])
    r = A[-r_cnt]
    cnt += 1
    r_cnt += 1    
    if cnt == N:
        break

    ans1 += abs(l-A[l_cnt])
    l = A[l_cnt]
    cnt += 1
    l_cnt += 1
    if cnt == N:
        break

    ans1 += abs(r-A[l_cnt])
    r = A[l_cnt]
    cnt += 1
    l_cnt += 1
    if cnt == N:
        break

l,r = A[-1],A[-1]
cnt = 1
l_cnt = 0
r_cnt = 2
ans2 = 0
while True:
    ans2 += abs(l-A[l_cnt])
    l = A[l_cnt]
    cnt += 1
    l_cnt += 1
    if cnt == N:
        break

    ans2 += abs(r-A[l_cnt])
    r = A[l_cnt]
    cnt += 1
    l_cnt += 1
    if cnt == N:
        break

    ans2 += abs(l-A[-r_cnt])
    l = A[-r_cnt]
    cnt += 1
    r_cnt += 1
    if cnt == N:
        break

    ans2 += abs(r-A[-r_cnt])
    r = A[-r_cnt]
    cnt += 1
    r_cnt += 1    
    if cnt == N:
        break

print(max(ans1,ans2))

Solution (Python):
from collections import deque
import copy

N = int(input())
a = [int(input()) for i in range(N)]
a.sort()
b = copy.copy(a)

A = deque(a)

r = A[0]
l = A.popleft()

ans = 0
while True:
    if len(A) == 0:
        break
    c = A.pop()
    ans += abs(l-c)
    l = c
    if len(A) == 0:
        break
    c = A.pop()
    ans += abs(r-c)
    r = c
    if len(A) == 0:
        break
    c = A.popleft()
    ans += abs(l-c)
    l = c
    if len(A) == 0:
        break
    c = A.popleft()
    ans += abs(r-c)
    r = c

B = deque(b)
r = B[-1]
l = B.pop()
ans2 = 0
while True:
    if len(B) == 0:
        break
    c = B.popleft()
    ans2 += abs(l-c)
    l = c
    if len(B) == 0:
        break
    c = B.popleft()
    ans2 += abs(r-c)
    r = c
    if len(B) == 0:
        break
    c = B.pop()
    ans2 += abs(l-c)
    l = c
    if len(B) == 0:
        break
    c = B.pop()
    ans2 += abs(r-c)
    r = c
print(max(ans,ans2))

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
L, R = A[0], A[N-1]
S = R - L
x, y = 1, N - 2
while x <= y:
  a, b, c, d = abs(L-A[y]), abs(L-A[x]), abs(R-A[y]), abs(R-A[x])
  M = max(a, b, c, d)
  if M == a:
    L = A[y]
    y -= 1
    S += a
  elif M == b:
    L = A[x]
    x += 1
    S += b
  elif M == c:
    R = A[y]
    y -= 1
    S += c
  elif M == d:
    R = A[x]
    x += 1
    S += d
print(S)

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
ans = [0]*2
for i in range(n):
    if i%2==0:
        ans[0] -= 2*a[i//2]
    else:
        ans[0] += 2*a[n-1-i//2]
    
    if i%2==0:
        ans[1] += 2*a[n-1-i//2]
    else:
        ans[1] -= 2*a[i//2]
if n%2==0:
    ans[0] +=a[n//2-1]
    ans[0] -=a[n//2]
    ans[1] +=a[n//2-1]
    ans[1] -=a[n//2]
else:
    ans[0] +=a[n//2]
    ans[0] +=a[n//2-1]
    ans[1] -=a[n//2]
    ans[1] -=a[n//2+1]
print(max(ans))

Solution (Python):
import numpy as np
n = int(input())
A =sorted([int(input()) for _ in range(n)])
l = n//2
if n%2:
  a = 2*sum(A[n-(l-1):]) + A[n-l] + A[n-(l+1)] - 2*sum(A[:n-(l+1)])
  b = 2*sum(A[n-l:]) - A[n-(l+1)] - A[n-(l+2)] - 2*sum(A[:n-(l+2)])
  print(max(a, b))
else:
  t = 2*sum(A[n-(l-1):]) + A[n-l] - A[n-(l+1)] - 2*sum(A[:n-(l+1)])
  print(t)

Solution (Python):
N, *A = map(int, open(0))

A.sort()

if N % 2 == 1:
    L, M, R = A[:N // 2], A[N // 2], A[N // 2 + 1:]
    print((sum(R) - sum(L)) * 2 + max(- M + L[-1], M - R[0]))
else:
    L, R = A[:N // 2], A[N // 2:]
    print((sum(R) - sum(L)) * 2 - R[0] + L[-1])

Solution (Python):
from collections import deque
n=int(input())
a=[int(input()) for i in range(n)]
a.sort()
q=deque()
for i in range(n//2):
  if i%2==0:
    q.appendleft(a[n-i-1])
    q.append(a[i])
  else:
    q.appendleft(a[i])
    q.append(a[n-i-1])
ans=0
q1=list(q)
if n%2==0:
  for i in range(n-1):
    ans+=abs(q1[i]-q1[i+1])
  print(ans)
else:
  for i in range(len(q1)-1):
    ans+=abs(q1[i]-q1[i+1])
  print(ans+max(abs(a[n//2]-q1[0]),abs(a[n//2]-q1[len(q1)-1])))

Solution (Python):
def main():
  N, *A = map(int, open(0).read().split())
  A.sort()

  if N % 2:
    array1 = [-2] * (N // 2) + [1] * 2 + [2] * (N // 2 - 1)
    array2 = [-2] * (N // 2 - 1) + [-1] * 2 + [2] * (N // 2)
  
    ret1 = 0
    ret2 = 0
    for i, j, k in zip(A, array1, array2):
      ret1 += i * j
      ret2 += i * k
    ret = max(ret1, ret2)

  else:
    array1 = [-2] * (N // 2 - 1) + [-1] + [1] + [2] * (N // 2 - 1)
  
    ret = 0
    for i, j in zip(A, array1):
      ret += i * j
  
  print(ret)

  
if __name__=="__main__":
  main()

Solution (Python):
def main():
  N, *A = map(int, open(0).read().split())
  A.sort()

  if N % 2:
    array1 = [-2] * (N // 2) + [1] * 2 + [2] * (N // 2 - 1)
    array2 = [-2] * (N // 2 - 1) + [-1] * 2 + [2] * (N // 2)
  
    ret1 = 0
    ret2 = 0
    for i in range(N):
      ret1 += A[i]*array1[i] 
      ret2 += A[i]*array2[i]
    ret = max(ret1, ret2)

  else:
    array1 = [-2] * (N // 2 - 1) + [-1] + [1] + [2] * (N // 2 - 1)
  
    ret = 0
    for i in range(N):
      ret += A[i]*array1[i] 
  
  print(ret)

  
if __name__=="__main__":
  main()

Solution (Python):
import numpy as np


def main():
  N, *A = map(int, open(0).read().split())
  A.sort()
  A = np.array(A)

  if N % 2:
    array1 = np.array([-2] * (N // 2) + [1] * 2 + [2] * (N // 2 - 1))
    array2 = np.array([-2] * (N // 2 - 1) + [-1] * 2 + [2] * (N // 2))
  
    ret1 = np.dot(A, array1)
    ret2 = np.dot(A, array2)
    ret = max(ret1, ret2)

  else:
    array1 = np.array([-2] * (N // 2 - 1) + [-1] + [1] + [2] * (N // 2 - 1))
  
    ret = np.dot(A, array1)
  
  print(ret)
  
if __name__=="__main__":
  main()

Solution (Python):
N, *A = map(int, open(0).read().split())
A.sort()

if N % 2:
  array1 = [-2] * (N // 2) + [1] * 2 + [2] * (N // 2 - 1)
  array2 = [-2] * (N // 2 - 1) + [-1] * 2 + [2] * (N // 2)
  
  ret1 = 0
  ret2 = 0
  for i in range(N):
    ret1 += A[i]*array1[i] 
    ret2 += A[i]*array2[i]
  ret = max(ret1, ret2)

else:
  array1 = [-2] * (N // 2 - 1) + [-1] + [1] + [2] * (N // 2 - 1)
  
  ret = 0
  for i in range(N):
    ret += A[i]*array1[i] 
  
print(ret)

Solution (Python):
def calc(A):
    res = 0
    
    for i in range(N-1):
        res += abs(A[i+1]-A[i])
    
    return res

N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()

if N%2==0:
    l1 = A[:N//2]
    l2 = A[N//2:]
    l1.reverse()
    l2.reverse()
    B = [-1]*N
    
    for i in range(N):
        if i%2==0:
            B[i] = l1[i//2]
        else:
            B[i] = l2[i//2]
            
    ans = calc(B)
    print(ans)
else:
    l1 = A[:N//2]
    l2 = A[N//2:]
    B = [-1]*N
    B[0] = l2[0]
    B[-1] = l2[1]
    
    for i in range(1, N-1):
        if i%2==0:
            B[i] = l2[i//2+1]
        else:
            B[i] = l1[i//2]
    
    l1 = A[:N//2+1]
    l2 = A[N//2+1:]
    C = [-1]*N
    C[0] = l1[-1]
    C[-1] = l1[-2]
    
    for i in range(1, N-1):
        if i%2==0:
            C[i] = l1[i//2-1]
        else:
            C[i] = l2[i//2]
   
    ans = max(calc(B), calc(C))
    print(ans)

Solution (Python):
N = int(input())
a = [int(input()) for _ in range(N)]
a.sort()
if N == 2:
    print(a[-1] - a[0])
    exit()

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

Solution (Python):
N = int(input())
A = [0] * N

for i in range(N):
	A[i] = int(input())

A.sort()

ans = 0

for t in range(2):
	coef = [0] * N
	for i in range(N):
		k = 0
		if i == 0 or i == N-1:
			k = 1 
		else:
			k = 2
		if (t + i) % 2 == 1:
			k = -k
		coef[i] = k
	coef.sort()

	val = 0
	for i in range(N):
		val += coef[i] * A[i]

	ans = max(ans, val)

print(ans)

Solution (Python):
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    A.sort()
    from collections import deque

    def make1():
        d = deque(A)
        ret = deque([d.popleft()])
        for i in range((N-1)//2):
            if i & 1:
                j = d.popleft()
                k = d.popleft()
            else:
                j = d.pop()
                k = d.pop()
            if abs(ret[0] - j) < abs(ret[-1] - j):
                ret.appendleft(j)
                ret.append(k)
            else:
                ret.append(j)
                ret.appendleft(k)
        if len(d) == 1:
            j = d.pop()
            if abs(ret[0] - j) < abs(ret[-1] - j):
                ret.append(j)
            else:
                ret.appendleft(j)
        ans = 0
        for i in range(1, N):
            ans += abs(ret[i-1] - ret[i])
        return ans

    def make2():
        d = deque(A)
        ret = deque([d.pop()])
        for i in range((N-1)//2):
            if i & 1:
                j = d.pop()
                k = d.pop()
            else:
                j = d.popleft()
                k = d.popleft()
            if abs(ret[0] - j) < abs(ret[-1] - j):
                ret.appendleft(j)
                ret.append(k)
            else:
                ret.append(j)
                ret.appendleft(k)
        if len(d) == 1:
            j = d.pop()
            if abs(ret[0] - j) < abs(ret[-1] - j):
                ret.append(j)
            else:
                ret.appendleft(j)
        ans = 0
        for i in range(1, N):
            ans += abs(ret[i-1] - ret[i])
        return ans

    print(max(make1(), make2()))


if __name__ == '__main__':
    main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
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
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LIN(N)
    
    def solve(odd):
        s1 = sorted(A)
        s2 = sorted(A,reverse=True)


        if odd:
            s1,s2 = s2,s1
        
        q = deque([s1.pop()])

        sign = False
        for i in range(N):
            if sign:
                v = s1.pop()
            else:
                v = s2.pop()
            q.appendleft(v)

            if len(s1)+len(s2)<=N:
                break
            
            if sign:
                v = s1.pop()
            else:
                v = s2.pop()
            q.append(v)
            
            if len(s1)+len(s2)<=N:
                break
            sign ^= 1

        res = 0
        before = q[0]
        for a in q:
            res += abs(before-a)
            before = a

        return res 

    print(max(solve(1),solve(0)))
if __name__ == '__main__':
    main()

Solution (Python):














N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

A.sort()



if N & 1 == 0:
    now = A[N // 2]
    ans = 0
    for i in range(N // 2):
        for idx in [i, -(i + 1)]:
            if idx == -N // 2:
                break
            ans += abs(now - A[idx])
            now = A[idx]
    print(ans)
else:  
    
    

    now = A[N // 2]
    ans1 = 0
    for i in range(N // 2):
        for idx in [i, -(i + 1)]:
            ans1 += abs(now - A[idx])
            now = A[idx]

    now = A[N // 2]
    ans2 = 0
    for i in range(N // 2):
        for idx in [-(i + 1), i]:
            ans2 += abs(now - A[idx])
            now = A[idx]
    
    print(max(ans1, ans2))

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

a1 = []
a2 = []
a1.append(a[n//2])
a2.append(a[n//2])

for i in range((n-1)//2):
    a1.append(a[i])
    a1.append(a[n-i-1])
    
    a2.append(a[n-i-1])
    a2.append(a[i])
if not n%2:
    a1.append(a[n//2-1])
    a2.append(a[n//2-1])

ans1 = 0
ans2 = 0
for i in range(len(a1)-1):
    ans1 += abs(a1[i+1] -a1[i])
    ans2 += abs(a2[i+1]-a2[i])
print(max(ans1,ans2))

Solution (Python):
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
import scipy
from collections import deque
from math import sqrt
from math import floor


"""
need to consider the case that ticket is not enough to lower everything
"""

N = gi()
A = [0] * N
ais = [0] * N

for i in range(N):
    A[i] = gi()

A.sort()
base = 0
half_i = N // 2

for i in range(half_i):
    base -= 2 * A[i]

for i in range(half_i, N):
    base += 2 * A[i]

el = 0
ol_l = 0
ol_h = 0

if N % 2 == 0:
    el = base - A[half_i] + A[half_i - 1]

if (N >= 3 and N % 2):
    ol_l = base - 3 * A[half_i] + A[half_i - 1]
    ol_h = base - A[half_i] - A[half_i + 1]

print(max(el, ol_l, ol_h))

Solution (Python):

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
A.sort()
L1, L2 = [0] * N, [0] * N
L1[0] = A[N//2]
L2[0] = A[N//2]
for i in range(1, N):
    if i % 2 == 0:
        L1[i] = A[i//2-1]
        L2[i] = A[-i//2]
    else:
        L1[i] = A[-i//2]
        L2[i] = A[i//2]
a1, a2 = 0, 0
for i in range(N-1):
    a1 += abs(L1[i] - L1[i+1])
    a2 += abs(L2[i] - L2[i+1])
print(max(a1, a2))

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]

A.sort()
A = A[::-1]

if N % 2:
  a = sum(A[:(N - 1) // 2])
  b = sum(A[(N - 1) // 2:(N - 1) // 2 + 2])
  c = sum(A[(N - 1) // 2 + 2:])
  answer = a * 2 + b * (-1) + c * (-2)
  a = sum(A[:(N - 3) // 2])
  b = sum(A[(N - 3) // 2:(N - 3) // 2 + 2])
  c = sum(A[(N - 3) // 2 + 2:])
  answer = max(answer, a * 2 + b + c * (-2))
else:
  a = sum(A[:(N - 2) // 2])
  b = A[(N - 2) // 2:(N - 2) // 2 + 2]
  c = sum(A[(N - 2) // 2 + 2:])
  answer = a * 2 + b[0] - b[1] + c * (-2)
print(answer)

Solution (Python):
n=int(input())
a=[int(input())for _ in range(n)]
if n==2:print(abs(a[0]-a[1]));exit()
f=[-1]
for i in range(1,n-1-(n%2==0)):
  if i%2:f.append(2)
  else:f.append(-2)
if n%2:f+=[-1]
else:f+=[-2,1]
b=[]
c=[]
for i in f:
  b.append(i)
  c.append(-i)
b.sort()
c.sort()
sb=sc=0
a.sort()
for i in range(n):
  sb+=a[i]*b[i]
  sc+=a[i]*c[i]
print(max(sb,sc))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)
a.sort()
if n%2 == 0:
    res = 0
    for i in range(n//2-1):
        res -= a[i] * 2
        res += a[n-i-1] * 2
    res += a[n//2] - a[n//2-1]
    print(res)
else:
    res_1 = 0
    res_2 = 0
    l = a[:n//2]
    r = a[n//2:]
    res_1 = sum(r)*2 - (r[0] + r[1]) - sum(l)*2 
    
    l = a[:n//2+1]
    r = a[n//2+1:]
    res_2 = sum(r)*2 - sum(l)*2 + l[-1]+l[-2]
    print(max(res_1, res_2))

Solution (Python):
from collections import deque
from copy import copy
N = int(input())
A = deque(sorted([int(input()) for _ in range(N)]))
A2 = copy(A)
d = deque()
d.append(A.popleft())
while True:
    try:
        d.append(A.pop())
        d.appendleft(A.pop())
        d.append(A.popleft())
        d.appendleft(A.popleft())
    except IndexError:
        break
ans = 0
for i in range(N-1):
    ans += abs(d[i]-d[i+1])
A = A2
d = deque()
d.append(A.pop())
while True:
    try:
        d.append(A.popleft())
        d.appendleft(A.popleft())
        d.append(A.pop())
        d.appendleft(A.pop())
    except IndexError:
        break
n = 0
for i in range(N-1):
    n += abs(d[i]-d[i+1])
print(max(ans, n))

Solution (Python):


N=int(input())
A=[0]*N
for i in range(N):
    A[i]=int(input())

A=sorted(A)

mf=0
ms=0
sf=0
ss=0
d=0
c=0
n=0


ml=N-1
mr=N-1
sl=0
sr=1
n=1
while(True):
    if(n==N):break
    d+=(A[ml]-A[sl])
    ml=mr-1
    n+=1
    if(n==N):break
    d+=(A[mr]-A[sr])
    mr=ml-1
    n+=1
    if(n==N):break
    d+=(A[ml]-A[sl])
    sl=sr+1
    n+=1
    if(n==N):break
    d+=(A[mr]-A[sr])
    sr=sl+1
    n+=1

ml=N-1
mr=N-2
sl=0
sr=0
n=1
while(True):
    if(n==N):break
    c+=(A[ml]-A[sl])
    sl=sr+1
    n+=1
    if(n==N):break
    c+=(A[mr]-A[sr])
    sr=sl+1
    n+=1
    if(n==N):break
    c+=(A[ml]-A[sl])
    ml=mr-1
    n+=1
    if(n==N):break
    c+=(A[mr]-A[sr])
    mr=ml-1
    n+=1

print(max(d,c))

Solution (Python):
def examA():
    S = SI()
    if len(S)==3:
        ans = S[::-1]
    else:
        ans = S
    print(ans)
    return

def examB():
    A, B, K = LI()
    for i in range(K):
        if i%2==0:
            B +=A//2
            A //=2
        else:
            A +=B//2
            B //=2
    print(A,B)
    return

def examC():
    N = I()
    A = [I() for _ in range(N)]
    A.sort()
    A1 = A[:N//2]; A2 = A[N//2:]
    ans = 0; cur = 0
    for i in range(len(A2)):
        if i<len(A1):
            cur +=(A2[i]-A1[i])
        if i-1>=0:
            cur +=(A2[i]-A1[i-1])
    if N%2==1:
        cur += (A2[-1] - A2[1])
    ans = max(ans,cur)


    if N%2==1:
        A1 = A[:1+(N//2)]; A2 = A[1+(N//2):]
        cur = 0
        for i in range(len(A1)):
            if i < len(A2):
                cur += (A2[i] - A1[i])
            if i - 1 >= 0:
                cur += (A2[i-1] - A1[i])
        cur +=(A1[-2]-A1[0])
        ans = max(ans, cur)

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
A = sorted(A)

ans1 = 0
l = 0
r = N-1
for i in range(N-2):
    if i%2 == 0:
        ans1 += 2 * A[r]
        r -= 1
    else:
        ans1 += -2 * A[l]
        l += 1
if N%2 == 0:
    ans1 -= min(A[l], A[r])
    ans1 += max(A[l], A[r])
else:
    ans1 -= (A[l] + A[r])

ans2 = 0
l = 0
r = N-1
for i in range(N-2):
    if i%2 == 1:
        ans2 += 2 * A[r]
        r -= 1
    else:
        ans2 += -2 * A[l]
        l += 1
if N%2 == 0:
    ans2 -= min(A[l], A[r])
    ans2 += max(A[l], A[r])
else:
    ans2 += (A[l] + A[r])

print(max(ans1,ans2))

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
N = int(input())
a = []
for _ in range(N):
  a.append(int(input()))
sa = dq(sorted(a))
res = 0
x = [0] * N
x[0] = sa[N // 2]
for i in range(1, N):
  if i % 2 == 0:
    x[i] = sa.popleft()
  else:
    x[i] = sa.pop()

for i in range(N - 1): res += abs(x[i + 1] - x[i])
res2 = 0
sa = dq(sorted(a))
x = [0] * N
x[0] = sa[-N // 2]
for i in range(1, N):
  if i % 2:
    x[i] = sa.popleft()
  else:
    x[i] = sa.pop()
for i in range(N - 1): res2 += abs(x[i + 1] - x[i])
print(max(res, res2))