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):
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):
import sys
n = int(input())
ls = [0] * n
for i in range(n):
    ls[i] = int(input())
ls.sort()

if n == 2:
    print(abs(ls[0]-ls[1]))
    sys.exit()
if n % 2 == 1:
    
    smaller = ls[:n//2+1]
    bigger = ls[n//2+1:]
    diff_1 = 2 * sum(bigger) - 2*sum(smaller) + smaller[-1] + smaller[-2]
    
    smaller = ls[:n//2]
    bigger = ls[n//2:]
    diff_2 = -2 * sum(smaller) + 2 * sum(bigger) - bigger[0] - bigger[1]
    diff = max(diff_1,diff_2)
else:
    smaller = ls[:n//2]
    bigger = ls[n//2:]
    diff = 2 * sum(bigger) - min(bigger) - 2 * sum(smaller) + max(smaller)

print(diff)

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

    for i in range(N//2,N):
        ans += 2*A[i]
    ans -= A[N//2]

    print(ans)

else:
    for i in range((N-1)//2):
        a -= 2*A[i]
    
    for i in range((N-1)//2,N):
        a += 2*A[i]
    
    a -= A[(N-1)//2]
    a -= A[(N-1)//2+1]

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

    b += A[(N-1)//2]+A[(N-1)//2-1]
    print(max(a,b))

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

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
As = sorted(A)
lowIdx = 0
highIdx = len(As)-1


l = As[lowIdx]
r = As[highIdx]
diff = r-l
lowIdx+=1
highIdx-=1

while lowIdx <= highIdx:
    low = As[lowIdx]
    high = As[highIdx]
    rHigh = abs(r - As[highIdx])
    lHigh = abs(l - As[highIdx])
    rLow = abs(r - As[lowIdx])
    lLow = abs(l - As[lowIdx])
    if rHigh >= max(lHigh, rLow, lLow):
        diff += rHigh
        r = high
        highIdx -= 1
    elif lHigh >= max(rLow, lLow):
        diff += lHigh
        l = high
        highIdx -= 1
    elif rLow >= lLow:
        diff += rLow
        r = low
        lowIdx += 1
    else:
        diff += lLow
        l = low
        lowIdx += 1

print(diff)

Solution (Python):

def main():
    N, *A = map(int, open(0).read().split())
    A.sort()
    if N & 1:
        low, high, mid = A[: N // 2], A[N // 2 + 1 :], A[N // 2]
        x = (sum(high) - sum(low)) * 2 - mid + low[-1]
        y = (sum(high) - sum(low)) * 2 + mid - high[0]
        ans = max(x, y)
    else:
        low, high = A[: N // 2], A[N // 2 :]
        ans = (sum(high) - sum(low)) * 2 - high[0] + low[-1]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):



def main():
    n = int(input())
    a = sorted([int(input()) for _ in range(n)], reverse=True)
    ans = 0
    center = n // 2

    
    
    
    
    
    
    if n % 2 == 0:
        ans += sum(a[:center - 1]) * 2
        ans += a[center - 1]
        ans -= a[center]
        ans -= sum(a[center + 1:]) * 2
    else:
        ans1 = 0
        ans1 += sum(a[:center - 1]) * 2
        ans1 += a[center - 1]
        ans1 += a[center]
        ans1 -= sum(a[center + 1:]) * 2

        ans2 = 0
        ans2 += sum(a[:center]) * 2
        ans2 -= a[center]
        ans2 -= a[center + 1]
        ans2 -= sum(a[center + 2:]) * 2
        ans = max(ans1, ans2)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    n = int(input())
    a = sorted([int(input()) for _ in range(n)], reverse=True)
    ans = 0
    center = n // 2

    
    
    
    
    
    
    if n % 2 == 0:
        ans += sum(a[:center - 1]) * 2
        ans += a[center - 1]
        ans -= a[center]
        ans -= sum(a[center + 1:]) * 2
    else:
        ans1 = 0
        ans1 += sum(a[:center - 1]) * 2
        ans1 += a[center - 1]
        ans1 += a[center]
        ans1 -= sum(a[center + 1:]) * 2

        ans2 = 0
        ans2 += sum(a[:center]) * 2
        ans2 -= a[center]
        ans2 -= a[center + 1]
        ans2 -= sum(a[center + 2:]) * 2
        ans = max(ans1, ans2)

    print(ans)


if __name__ == '__main__':
    main()

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

X = sorted(X)

M = []
m = []
for i in range(N // 2):
	M.append(X[-1 - i])
	m.append(X[i])
M = sorted(M)

if N % 2 == 0:
	n = N
else:
	n = N - 1
s = []
for i in range(n):
	if i % 2 == 0:
		s.append(M[i // 2])
	else:
		s.append(m[i // 2])
ans = 0
for i in range(n - 1):
	ans += abs(s[i + 1] - s[i])
if N % 2 == 1:
	ans += max(abs(X[N // 2] - s[0]), abs(X[N // 2] - s[-1]))
print(ans)

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

A.sort()

if N%2 == 0:
    l = N//2
    B1 = A[:l]
    B2 = A[l:]
    ans = 0
    for i in range(l):
        ans += (B2[i] - B1[i])*2
    ans -= B2[0] - B1[-1]
    print(ans)
else:
    l = N//2
    B1 = A[:l]
    B2 = A[l:]
    a1 = 0
    for i in range(l):
        a1 -= B1[i]*2
    for i in range(l+1):
        if i == 0 or i == 1:
            a1 += B2[i]
        else:
            a1 += B2[i]*2
    
    C1 = A[:l+1]
    C2 = A[l+1:]
    a2 = 0

    for i in range(l):
        a2 += C2[i]*2
    for i in range(l+1):
        if i == l-1 or i == l:
            a2 -= C1[i]
        else:
            a2 -= C1[i]*2
    print(max(a1, a2))

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

n = ni()
a = [ni() for _ in range(n)]

a.sort()

b = a.copy()
c = a.copy()


bdeq = deque(b)
bret = deque()

bret.append(bdeq.popleft())
push_small = False
while len(bdeq) > 1:
    if push_small:
        bret.append(bdeq.popleft())
        bret.appendleft(bdeq.popleft())
        push_small = False

    else:
        bret.append(bdeq.pop())
        bret.appendleft(bdeq.pop())
        push_small = True

if len(bdeq) > 0:
    if abs(bdeq[0] - bret[0]) > abs(bdeq[0] - bret[-1]):
        bret.appendleft(bdeq[0])
    else:
        bret.append(bdeq[0])


cdeq = deque(c)
cret = deque()

cret.append(cdeq.pop())
push_small = True
while len(cdeq) > 1:
    if push_small:
        cret.append(cdeq.popleft())
        cret.appendleft(cdeq.popleft())
        push_small = False

    else:
        cret.append(cdeq.pop())
        cret.appendleft(cdeq.pop())
        push_small = True

if len(cdeq) > 0:
    if abs(cdeq[0] - cret[0]) > abs(cdeq[0] - cret[-1]):
        cret.appendleft(cdeq[0])
    else:
        cret.append(cdeq[0])


bans = 0
for i in range(n-1):
    bans += abs(bret[i] - bret[i+1])

cans = 0
for i in range(n-1):
    cans += abs(cret[i] - cret[i+1])

print(max(bans, cans))

Solution (Python):
n=int(input())
a=[int(input()) for i in range(n)]
a.sort()
x=0;y=0
if n%2==0:
  for i in range(n):
    if i<n//2-1:
      x-=a[i]*2
    elif i==n//2-1:
      x-=a[i]
    elif i==n//2:
      x+=a[i]
    else:
      x+=a[i]*2
  print(x)
else:
  for i in range(n):
    if i<n//2:
      x-=a[i]*2
    elif i==n//2:
      x+=a[i]
    elif i==n//2+1:
      x+=a[i]
    else:
      x+=a[i]*2
  for i in range(n):
    if i<n//2-1:
      y-=a[i]*2
    elif i==n//2-1:
      y-=a[i]
    elif i==n//2:
      y-=a[i]
    else:
      y+=a[i]*2
  print(max(x,y))

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

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
A.sort(reverse=True)
mae=0
ushiro=0
if N%2==0:
    if N>3:
        for i in range(N//2-1):
            mae+=A[i]
        for i in range(N//2+1,N):
            ushiro+=A[i]
    a0=A[N//2-1]
    a1=A[N//2]
    print((mae-ushiro)*2+a0-a1)
else:
    if N>3:
        for i in range(N//2-1):
            mae+=A[i]
        for i in range(N//2+2,N):
            ushiro+=A[i]
    a0=A[N//2-1]
    a1=A[N//2]
    a2=A[N//2+1]
    print((mae-ushiro)*2+max(2*a0-a1-a2,a0+a1-2*a2))

Solution (Python):
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
A = sorted(A, reverse=True)
L, R = A[0], A[0]
A.pop(0)
num = 0
for i in range(N - 1):
    k1 = A[-1]
    k2 = A[0]
    tmp = []
    tmp.append(abs(L - k1))
    tmp.append(abs(L - k2))
    tmp.append(abs(R - k1))
    tmp.append(abs(R - k2))
    ma = max(tmp)
    if ma == abs(L - k1):
        num += abs(L - k1)
        A.pop(-1)
        L = k1
    elif ma == abs(L - k2):
        num += abs(L - k2)
        A.pop(0)
        L = k2
    elif ma == abs(R - k1):
        num += abs(R - k1)
        A.pop(-1)
        R = k1
    else:
        num += abs(R - k2)
        A.pop(0)
        R = k2

print(num)

Solution (Python):
N = int(input())
lis = [int(input()) for n in range(N)]
lis = sorted(lis)
half = len(lis) // 2
low = lis[:half]
high = lis[:half-1:-1]
    

def output(low_lis, high_lis):
    ll, hl = len(low_lis), len(high_lis)
    if ll > hl:
        return calc(low_lis, high_lis)
    return calc(high_lis, low_lis)

def calc(lis1, lis2):
    left = lis1[0]
    right = left
    res = 0
    try:
        for n in range((len(lis1) + 1) // 2):
            res += abs(left - lis1[2*n])
            res += abs(right - lis2[2*n])
            res += abs(lis1[2*n + 1] - lis2[2*n])
            res += abs(lis2[2*n+1] - lis1[2*n])
            right = lis1[2*n + 1]
            left = lis2[2*n+1]
        return res
    except IndexError:
        return res

res1 = output(low, high)
res2 = 0
if len(lis) % 2:
    low = lis[:half + 1]
    high = lis[:half:-1]
    res2 = output(low, high)
    
print(max(res1, res2))

Solution (Python):
import numpy as np
N = int(input())
A = list(int(input())for i in range(N))
A.sort()
A = np.array(A)
C1,C2 = [],[]
if N%2 == 1:
    C1 = [-2]*int(N/2-1)+[-1]*2+[2]*int(N/2)
    C2 = [-2]*int(N/2)+[1]*2+[2]*int(N/2-1)
else:
    C1 = [-2]*int(N/2-1)+[-1]+[1]+[2]*int(N/2-1)
    C2 = [-2]*int(N/2-1)+[-1]+[1]+[2]*int(N/2-1)
C1 = np.array(C1)
C2 = np.array(C2)
ans = max(sum(A*C1),sum(A*C2))
print(ans)

Solution (Python):


import sys
input=sys.stdin.readline
from collections import deque
N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
if N%2==0:
    ans=2*(-1*sum(A[0:N//2])+sum(A[N//2:N]))
    ans+=A[N//2-1]-A[N//2]
elif N%2==1:
    ans=2*(-1*sum(A[0:N//2])+sum(A[1+N//2:N]))
    a1,a2,a3=A[N//2-1],A[N//2],A[N//2+1]
    if 2*a2-a1-a3>=0:
        ans+=a2-a3
    else:
        ans+=a1-a2
print(ans)

Solution (Python):

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

B = sorted(A)




ans = (
    2 * sum(
        B[-(i + 1)] - B[i]
        for i in range(N // 2)
    ) - min(
        B[N // 2] - B[N // 2 - 1],
        B[N // 2 + 1] - B[N // 2] if N % 2 == 1 else 10**18
    )
)

print(ans)

Solution (Python):

"""
Created on Mon Apr 15 22:46:42 2019

@author: Yamazaki Kenichi
"""
import math
N = int(input())
A = [int(input()) for i in range(N)]

A.sort()

temp1,temp2 = 0,0
if N%2 != 55:
    temp1 += A[-1]+A[-2]-2*A[0]

    for i in range(N//2-1):
        temp1 += A[-1-(math.ceil(i/2)*2)] - A[(i//2*2)+1]
        temp1 += A[-2-(math.ceil(i/2)*2)] - A[(i//2*2)+2]

    temp2 += 2*A[-1]-A[0]-A[1]

    for i in range(N//2-1):
        temp2 += A[-2-(i//2*2)] - A[(math.ceil(i/2)*2)]
        temp2 += A[-3-(i//2*2)] - A[(math.ceil(i/2)*2)+1]

print(max(temp1,temp2))

Solution (Python):

"""
Created on Mon Apr 15 22:46:42 2019

@author: Yamazaki Kenichi
"""
import math
N = int(input())
A = [int(input()) for i in range(N)]

A.sort()

temp1,temp2 = 0,0
if N%2 != 55:
    temp1 += A[-1]+A[-2]-2*A[0]

    for i in range(N//2-1):
        temp1 += A[-1-(math.ceil(i/2)*2)] - A[(i//2*2)+1]
        temp1 += A[-2-(math.ceil(i/2)*2)] - A[(i//2*2)+2]

    temp2 += 2*A[-1]-A[0]-A[1]

    for i in range(N//2-1):
        temp2 += A[-2-(i//2*2)] - A[(math.ceil(i/2)*2)]
        temp2 += A[-3-(i//2*2)] - A[(math.ceil(i/2)*2)+1]

print(max(temp1,temp2))

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

a = len(A)
if a%2==0:
  answer = 2 * sum(A[a//2+1:]) + A[a//2] - A[a//2-1] - 2* sum(A[:a//2-1])
  
if a%2==1:
  b = a//2
  if 2*A[b] - A[b-1] - A[b+1]<0:
    answer = 2*sum(A[b+1:]) - A[b] - A[b-1] - 2*sum(A[:b-1])
  else:
    answer = A[b] + A[b+1] + 2*sum(A[b+2:]) - 2*sum(A[:b])  
  
print(answer)

Solution (Python):
N = input()
a = []
for i in range(N):
	a.append(input())
a.sort()
if(N % 2 == 1):
	print((sum(a[(N+1)/2:])-sum(a[:(N+1)/2-1]))*2-min([a[(N+1)/2-1]-a[(N+1)/2-2],a[(N+1)/2]-a[(N+1)/2-1]]))
else:
	print((sum(a[N/2:])-sum(a[:N/2]))*2-(a[N/2]-a[N/2-1]))

Solution (Python):
N = input()
a = []
for i in range(N):
	a.append(input())
a.sort()
if(N % 2 == 1):
	print((sum(a[N/2+1:])-sum(a[:N/2]))*2-min([a[N/2]-a[N/2-1],a[N/2+1]-a[N/2]]))
else:
	print((sum(a[N/2:])-sum(a[:N/2]))*2-(a[N/2]-a[N/2-1]))

Solution (Python):
n = int(input())
l = [int(input()) for _ in range(n)]
l.sort()
if n%2:
  s1 = l[:(n-1)//2]
  b1 = l[(n-1)//2:]
  t1 = sum(b1)*2 - sum(s1)*2 -sum(b1[:2])
  s2 = l[:(n+1)//2]
  b2 = l[(n+1)//2:]
  t2 = sum(b2)*2 - sum(s2)*2 + sum(s2[-2:])
  t = max(t1,t2)
else:
  s = l[:n//2]
  b = l[n//2:]
  t = sum(b)*2 - sum(s)*2 -b[0] + s[-1]
print(t)

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

A=sorted(A)
B=A[:]

ans=0

top=A[0]
bottom=A[0]
tmp=0
turn=True
del A[0]
while  A:
  if len(A)==1:
    tmp+=max(abs(top-A[0]),abs(bottom-A[0]))
    break
    pass
  if turn:
    a,b=A[-2],A[-1]
  else:
    a,b=A[0:2]
    
  if abs(a-bottom)+abs(b-top)<abs(a-top)+abs(b-bottom):
    a,b=b,a
  tmp+=abs(a-bottom)+abs(b-top)
  bottom,top=a,b
  if turn:
    del A[-1]
    del A[-1]
  else:
    del A[0]
    del A[0]
  turn=not turn

ans=tmp
A=B
top=A[-1]
bottom=A[-1]
tmp=0
del A[-1]
turn = True
while  A:
  
  if len(A)==1:
    tmp+=max(abs(top-A[0]),abs(bottom-A[0]))
    break
    pass
  if turn:
    a,b=A[0],A[1]
  else:
    a,b=A[-1],A[-2]
    
  if abs(a-bottom)+abs(b-top)<abs(a-top)+abs(b-bottom):
    a,b=b,a
  tmp+=abs(a-bottom)+abs(b-top)
  bottom,top=a,b
  if turn:
    del A[0] 
    del A[0]
  else:
    del A[-1]
    del  A[-1]
  turn= not turn

ans=max(ans,tmp)
print(ans)

Solution (Python):
n,*a=map(int,open(0).readlines())
a.sort()
if n%2:
  b=a[:n//2]
  c=a[n//2:]
  for i in range(n//2):
    b[i]*=2
  for i in range(2,n//2+1):
    c[i]*=2
  m=sum(c)-sum(b)
  b=a[:n//2+1]
  c=a[n//2+1:]
  for i in range(n//2-1):
    b[i]*=2
  for i in range(n//2):
    c[i]*=2
  m=max(m,sum(c)-sum(b))
else:
  b=a[:n//2]
  c=a[n//2:]
  for i in range(n//2-1):
    b[i]*=2
  for i in range(1,n//2):
    c[i]*=2
  m=sum(c)-sum(b)
print(m)

Solution (Python):
n,*a=map(int,open(0).readlines())
a.sort()
if n%2:
  b=a[:n//2]
  c=a[n//2:]
  for i in range(n//2):
    b[i]*=2
  for i in range(2,n//2+1):
    c[i]*=2
  m=sum(c)-sum(b)
  b=a[:n//2+1]
  c=a[n//2+1:]
  for i in range(n//2-1):
    b[i]*=2
  for i in range(n//2):
    c[i]*=2
  m=max(m,sum(c)-sum(b))
else:
  b=a[:n//2]
  c=a[n//2:]
  for i in range(n//2-1):
    b[i]*=2
  for i in range(1,n//2):
    c[i]*=2
  m=sum(c)-sum(b)
print(m)

Solution (Python):
n = int(input())
a = sorted(int(input()) for i in range(n))
median = a[(n-1)//2]
ans = 0
for i in range(n):
    ans += 2*abs(a[i] - median)
if n % 2 == 0:
    ans -= abs(a[(n-1)//2+1] - median)
else:
    ans -= min(abs(a[(n-1)//2+1] - median), abs(a[(n-1)//2-1] - median))
print(ans)

Solution (Python):
import numpy as np

import itertools
n = int(input())
a = []
for i in range(n):
    a.append(input())

a = [int(m) for m in a]

a.sort()
if n % 2 == 0:
    small = []
    big = []
    for i in range(n):
        if i < n // 2:
            small.append(a[i])
        else:
            big.append(a[i])
    print(2 * (sum(big) - sum(small)) - big[0] + small[n // 2 - 1])
else:
    small = []
    big = []
    for i in range(n):
        if i < n // 2:
            small.append(a[i])
        elif i > n // 2:
            big.append(a[i])
    print(max(2 * (sum(big) - sum(small)) - big[0] + a[n // 2], 2 * (sum(big) - sum(small)) + small[n // 2 - 1] - a[n // 2]))

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

if N % 2 == 0:
    X = [-2] * ((N - 2) // 2) + [-1, 1] + [2] * ((N - 2) // 2)
    ans = sum([a * x for a, x in zip(A, X)])
    print(ans)
else:
    X1 = [-2] * ((N - 2) // 2 + 1) + [1, 1] + [2] * ((N - 2) // 2)
    X2 = [-2] * ((N - 2) // 2) + [-1, -1] + [2] * ((N - 2) // 2 + 1)
    ans1 = sum([a * x for a, x in zip(A, X1)])
    ans2 = sum([a * x for a, x in zip(A, X2)])
    print(max(ans1, ans2))

Solution (Python):
from itertools import accumulate


class CoeffTable:
    def __init__(self, n):
        self.n = n
        if n == 2:
            (self.p2, self.p1, self.m1, self.m2) = (0, 1, 1, 0)
        if n % 2 == 0:
            self.p1 = self.m1 = 1
            self.p2 = self.m2 = (n - 1) // 2
        else:
            self.p1 = 0
            self.m1 = 2
            self.p2 = (n - 1) // 2
            self.m2 = (n - 2) // 2

    def reverse(self):
        (self.p2, self.p1, self.m1, self.m2) = (
            self.m2,
            self.m1,
            self.p1,
            self.p2,
        )

    def cumsum(self):
        return list(accumulate([self.p2, self.p1, self.m1, self.m2]))



def main(n, seq):
    seq = sorted(seq, reverse=True)
    coeff = CoeffTable(n)
    cm = coeff.cumsum()
    ans1 = (
        2 * sum(seq[0 : cm[0]])
        + 1 * sum(seq[cm[0] : cm[1]])
        - 1 * sum(seq[cm[1] : cm[2]])
        - 2 * sum(seq[cm[2] : cm[3]])
    )
    coeff.reverse()
    rcm = coeff.cumsum()
    ans2 = (
        2 * sum(seq[0 : rcm[0]])
        + 1 * sum(seq[rcm[0] : rcm[1]])
        - 1 * sum(seq[rcm[1] : rcm[2]])
        - 2 * sum(seq[rcm[2] : rcm[3]])
    )
    ans = max(ans1, ans2)
    print(ans)
    return


if __name__ == "__main__":
    n = int(input())
    sample = []
    for _ in range(n):
        sample.append(int(input()))
    main(n, sample)

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
ans1,ans2=0,0
if N%2==0:
  ans1-=A[N//2-1]
  ans1-=2*sum(A[:N//2-1])
  ans1+=A[N//2]
  ans1+=2*sum(A[N//2+1:])
else:
  ans1-=A[N//2-1]+A[N//2]
  ans1-=2*sum(A[:N//2-1])
  ans1+=2*sum(A[N//2+1:])
  ans2-=2*sum(A[:N//2])
  ans2+=A[N//2]+A[N//2+1]
  ans2+=2*sum(A[N//2+2:])

print(max(ans1,ans2))

Solution (Python):
N=int(input())
a=[int(input()) for i in range(N)]
a.sort()
if N%2==0:
  m=N//2
  ans=-2*sum(a[:m-1])-a[m-1]+a[m]+2*sum(a[m+1:])
if N%2==1:
  m=N//2
  ans=-2*sum(a[:m-1])-a[m-1]-a[m]+2*sum(a[m+1:])
  ans=max(ans,-2*sum(a[:m])+a[m]+a[m+1]+2*sum(a[m+2:]))

print(ans)

Solution (Python):


N = int(input())
A = sorted([int(input()) for _ in range(N)], reverse=True)

mult = []
if N % 2 == 0:
    for i in range(N):
        if 0 <= i <= (N//2 - 1) - 1:
            mult.append(2)
        elif i == N // 2 - 1:
            mult.append(1)
        elif i == N // 2:
            mult.append(-1)
        else:
            mult.append(-2)
    ans = sum([a*m for a, m in zip(A, mult)])
else:
    mult1 = []
    mult2 = []
    for i in range(N):
        if 0 <= i <= (N//2 - 1) - 1:
            mult1.append(2)
        elif i == N // 2 - 1:
            mult1.append(1)
        elif i == N // 2:
            mult1.append(1)
        else:
            mult1.append(-2)
    for i in range(N):
        if 0 <= i <= (N//2 - 1):
            mult2.append(2)
        elif i == N // 2:
            mult2.append(-1)
        elif i == N // 2 + 1:
            mult2.append(-1)
        else:
            mult2.append(-2)
    ans = max(sum([a*m for a, m in zip(A, mult1)]), sum([a*m for a, m in zip(A, mult2)]))
print(ans)

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

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

ans = 0

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

print(ans)

Solution (Python):
n=int(input())
l=[int(input()) for _ in range(n)]
l.sort()
m=sorted((-1)**(i+1) if i==0 or i==n-1 else 2*((-1)**(i+1)) for i in range(n))
f=lambda x,y:x*y
a=abs(sum(map(f,l,m)))
b=abs(sum(map(f,l[::-1],m)))
print(max(a,b))

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

i = 0 ; j = n-1; last = j;
ret = ret2 = 0
diff = 10**9

while i != j:
    last = j
    ret += a[j] - a[i]
    diff = min(diff, a[j] - a[i])
    
    i+=1
    if i==j: break
    last = i
    ret += a[j] - a[i]
    diff = min(diff, a[j] - a[i])

    j-=1
ret += a[last] - a[0]
diff = min(diff, a[last] - a[0])
ret -= diff

i = 0 ; j = n-1; last = j;

while i != j:
    last = i
    ret2 += a[j] - a[i]
    diff = min(diff, a[j] - a[i])
    
    j-=1
    if i==j: break
    last = j
    ret2 += a[j] - a[i]
    diff = min(diff, a[j] - a[i])

    i+=1
ret2 += a[n-1] - a[last]
diff = min(diff, a[n-1] - a[last])
ret2 -= diff

print(max(ret,ret2))

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

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

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

A.sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

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

a = sorted(a)

if n == 2:
    print(a[1] - a[0])
    exit()

res1 = a[n - 1] + a[n - 2] - (a[0] * 2)
p = n - 3
q = 1
mode = 0
while 1:
    
    if p < q:
        break
    elif p == q:
        if mode == 0:
            res1 += a[p + 2] - a[p]
        else:
            res1 += a[p] - a[p - 2]
        break
    else:
        if mode == 0:
            res1 += a[p + 1] + a[p + 2] - a[q] - a[q + 1]
            mode = 1
            q += 2
        else:
            res1 += a[p] + a[p - 1] - a[q - 1] - a[q - 2]
            mode = 0
            p -= 2

res2 = a[n - 1] * 2 - a[0] - a[1]
p = n - 2
q = 2
mode = 1
while 1:
    
    if p < q:
        break
    elif p == q:
        if mode == 0:
            res2 += a[p + 2] - a[p]
        else:
            res2 += a[p] - a[p - 2]
        break
    else:
        if mode == 0:
            res2 += a[p + 1] + a[p + 2] - a[q] - a[q + 1]
            mode = 1
            q += 2
        else:
            res2 += a[p] + a[p - 1] - a[q - 1] - a[q - 2]
            mode = 0
            p -= 2

print(max(res1, res2))

Solution (Python):
def f(As):
    Bs = [0] * N

    if N % 2:
        iB, d = 0, N - 1
    else:
        iB, d = 0, N - 2
    for A in As[N//2:]:
        Bs[iB] = A
        iB += d
        if d > 0:
            d = -d + 2
        else:
            d = -d - 2

    if N % 2:
        iB, d = 1, N - 3
    else:
        iB, d = N - 1, -(N - 2)
    for A in reversed(As[:N//2]):
        Bs[iB] = A
        iB += d
        if d > 0:
            d = -d + 2
        else:
            d = -d - 2

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

    return ans


N = int(input())
As = [int(input()) for _ in range(N)]

As.sort()

print(max(f(As), f(As[::-1])))

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

"""
N : even
a0 < a1 > a2 ... < aN-1
 -> 2(a1-a2+...-aN-2) - a0 + aN-1
a0 > a1 < a2 ... > aN-1
 -> 2(-a1+a2+...+aN-2) + a0 - aN-1
m = N//2 とすると
(a0, aN-1) = A[m-1], A[m]

N : odd
a0 < a1 > a2 ... > aN-1
 -> 2(a1-a2+...+aN-2) - a0 - aN-1
m = N//2とすると
(a0, aN-1) = A[m-1], A[m]

a0 > a1 < a2 ... < aN-1
 -> 2(-a1+a2-...-aN-2) + a0 + aN-1
m = N//2とすると
(a0, aN-1) = A[m], A[m+1]

"""
ans = 0
m = N // 2

if N%2 == 0:
  ans = sum(A[0:m-1]) * (-2) - A[m-1] + A[m] + sum(A[m+1:]) *2
else:
  a = sum(A[0:m-1]) * (-2) - A[m-1] - A[m] + sum(A[m+1:]) *2
  b = sum(A[0:m]) * (-2) + A[m] + A[m+1] + sum(A[m+2:]) *2
  ans = max(a,b)
  
print(ans)

Solution (Python):
import sys
N=int(input())
A=[int(input()) for i in range(N)]
B=sorted(A)
if N%2==0:
    C=B[:(N//2)]
    D=B[(N//2):]
    print(2*sum(D)-2*sum(C)+C[-1]-D[0])
    sys.exit()
C=B[:(N//2)]
D=B[((N//2)+1):]
s=B[(N//2)]
print(max(2*sum(D)-2*sum(C)+C[-1]-s,2*sum(D)-2*sum(C)+s-D[0]))

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

A.sort()

B=A[:N//2]
C=A[N//2:]





if len(B)>=2:
    B=[B[-1]]+B[:-2]+[B[-2]]

if len(C)>=2:
    C=[C[1]]+C[2:]+[C[0]]

if N%2==0:
    B,C=C,B



X=[]
b=0
c=0
while b<len(B) or c<len(C):
    if c<len(C):
        X.append(C[c])
    if b<len(B):
        X.append(B[b])
    b+=1
    c+=1


ANS=0
for i in range(1,N):
    ANS+=abs(X[i]-X[i-1])






B=A[:N//2+1]
C=A[N//2+1:]




if len(B)>=2:
    B=[B[-1]]+B[:-2]+[B[-2]]

if len(C)>=2:
    C=[C[1]]+C[2:]+[C[0]]

X=[]
b=0
c=0


while b<len(B) or c<len(C):
    if b<len(B):
        X.append(B[b])

    if c<len(C):
        X.append(C[c])

    b+=1
    c+=1


ANS2=0
for i in range(1,N):
    ANS2+=abs(X[i]-X[i-1])



print(max(ANS,ANS2))

Solution (Python):
N = int( input())
A = [ int( input()) for _ in range(N)]
ans1 = 0
A.sort()
nowL = A[0]
nowR = A[0]
for i in range(1,N):
    if i%4 == 3:
        ans1 += nowL - A[(i//4)*2+1]
        nowL = A[(i//4)*2+1]
    elif i%4 == 0:
        ans1 += nowR - A[(i//4)*2]
        nowR = A[(i//4)*2]
    elif i%4 == 1:
        ans1 += A[- (i//4)*2-1] - nowL
        nowL = A[-(i//4)*2 - 1]
    else:
        ans1 += A[- (i//4)*2 - 2] - nowR
        nowR = A[-(i//4)*2 - 2]
A = A[::-1]
ans2 = 0
nowL = A[0]
nowR = A[0]
for i in range(1,N):
    if i%4 == 1:
        ans2 += nowL - A[-(i//4)*2-1]
        nowL = A[-(i//4)*2-1]
    elif i%4 == 2:
        ans2 += nowR - A[-(i//4)*2-2]
        nowR = A[-(i//4)*2-2]
    elif i%4 == 3:
        ans2 += A[(i//4)*2+1] - nowL
        nowL = A[(i//4)*2+1]
    else:
        ans2 += A[(i//4)*2] - nowR
        nowR = A[(i//4)*2]

print( max(ans1, ans2))

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

As.sort(reverse=True)

if N % 2:
    ans = 2 * sum(As[:N//2 - 1]) - 2 * sum(As[N//2 + 2:])
    A1, A2, A3 = As[N//2 - 1:N//2 + 2]
    ans += max(A1 + A2 - 2*A3, 2*A1 - A2 - A3)
else:
    ans = 2 * sum(As[:N//2 - 1]) + As[N//2 - 1] - As[N//2] - 2 * sum(As[N//2 + 1:])

print(ans)

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

def calc_sum(replaced_list):
    max_sum = 0
    for i in range(len(replaced_list) - 1):
        left, right = replaced_list[i], replaced_list[i + 1]
        max_sum += abs(left - right) 
    return max_sum


def calc_replaced_even(N, A_list, left_mid, right_mid):
    replaced_list = [None] * N
    replaced_list[0] = A_list[left_mid]
    replaced_list[-1] = A_list[right_mid]
    for i in range(1, N//2):
        replaced_list[2 * i - 1] = A_list[-i]
        replaced_list[2 * i] = A_list[i - 1]
    return replaced_list


def calc_replaced_odd(N, A_list, left_mid, right_mid):
    replaced_list = [None] * N
    replaced_list[0] = A_list[left_mid]
    replaced_list[-1] = A_list[right_mid]
    if left_mid == N // 2 - 1:
        replaced_list[1] = A_list[-1]
        for i in range(1, left_mid + 1):
            replaced_list[2 * i] = A_list[i - 1]
            replaced_list[2 * i + 1] = A_list[-(i + 1)]
    else:
        replaced_list[-2] = A_list[0]
        for i in range(1, left_mid):
            replaced_list[2 * i - 1] = A_list[i]
            replaced_list[2 * i] = A_list[-i]
    return replaced_list


def calc_max_sum(replaced_list):
    max_sum = calc_sum(replaced_list)
    replaced_list[1:N-1] = replaced_list[1:N-1][::-1]
    return max(max_sum, calc_sum(replaced_list))


N = int(fin())
A_list = [int(fin()) for _ in range(N)]

A_list.sort()
replaced_list = [None] * N
if N % 2 == 0:
    left_mid = N // 2 - 1
    right_mid = N // 2
    replaced_list = calc_replaced_even(N, A_list, left_mid, right_mid)
    max_sum = calc_max_sum(replaced_list)
    print(max_sum)
else:
    
    max_sum = 0
    for left_mid, right_mid in ((N // 2 - 1, N // 2), (N // 2, N // 2 + 1)):
        replaced_list = calc_replaced_odd(N, A_list, left_mid, right_mid)
        max_sum = max(max_sum, calc_max_sum(replaced_list))
    print(max_sum)

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

arr = []
for i in range(N//2):
    arr.append(A[i])
    arr.append(A[-1-i])
if N%2:
    arr.append(A[N//2])

tmp = 0
for a,b in zip(arr,arr[1:]):
    tmp += abs(a-b)

ans = tmp
for i in range(N):
    arr.append(arr[i])
    gain = abs(arr[-1] - arr[-2]) - abs(arr[i] - arr[i+1])
    tmp += gain
    ans = max(tmp, ans)



arr = []
for i in range(N//2):
    arr.append(A[-1-i])
    arr.append(A[i])
if N%2:
    arr.append(A[N//2])

tmp = 0
for a,b in zip(arr,arr[1:]):
    tmp += abs(a-b)

for i in range(N):
    arr.append(arr[i])
    gain = abs(arr[-1] - arr[-2]) - abs(arr[i] - arr[i+1])
    tmp += gain
    ans = max(tmp, ans)

print(ans)

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

A.sort()

B=A[:N//2]
C=A[N//2:]





if len(B)>=2:
    B=[B[-1]]+B[:-2]+[B[-2]]

if len(C)>=2:
    C=[C[1]]+C[2:]+[C[0]]

if N%2==0:
    B,C=C,B



X=[]
b=0
c=0
while b<len(B) or c<len(C):
    if c<len(C):
        X.append(C[c])
    if b<len(B):
        X.append(B[b])
    b+=1
    c+=1


ANS=0
for i in range(1,N):
    ANS+=abs(X[i]-X[i-1])






B=A[:N//2+1]
C=A[N//2+1:]




if len(B)>=2:
    B=[B[-1]]+B[:-2]+[B[-2]]

if len(C)>=2:
    C=[C[1]]+C[2:]+[C[0]]

X=[]
b=0
c=0


while b<len(B) or c<len(C):
    if b<len(B):
        X.append(B[b])

    if c<len(C):
        X.append(C[c])

    b+=1
    c+=1


ANS2=0
for i in range(1,N):
    ANS2+=abs(X[i]-X[i-1])



print(max(ANS,ANS2))