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):
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])

def warshall_floyd(): 
    n,w = inpm() 
    d = [[10**10 for i in range(n)] for i in range(n)] 
    
    xyz=[]
    for i in range(w):
        x,y,z = inpm()
        x -= 1
        y -= 1
        xyz.append((x,y,z))
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return n,w,d,xyz

def main():
    n=inp()
    a=inplm(n)
    a.sort()
    n1 = 0
    n2 = 0
    minus = n//2

    for i in range(n):
        if i<minus-1:
            n1-=2*a[i]
        elif i==minus-1:
            n1-=(1+n%2)*a[i]
        elif i==minus:
            n1+=a[i]
        elif i==minus+1 and n%2==1:
            n1+=a[i]
        else:
            n1+=2*a[i]

    a.reverse()
    plus = n//2
    for i in range(n):
        if i<plus-1:
            n2+=2*a[i]
        elif i==plus-1:
            n2+=(1+n%2)*a[i]
        elif i==plus:
            n2-=a[i]
        elif i==plus+1 and n%2==1:
            n2-=a[i]
        else:
            n2-=2*a[i]

    print(max(n1,n2))

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
    
A.sort()
D = deque()
for i in range(N):
    if i%4==0:
        D.append(A[i//2])
    elif i%4==1:
        D.appendleft(A[-1-(i-1)//2])
    elif i%4==2:
        D.appendleft(A[i//2])
    else:
        D.append(A[-1-(i-1)//2])
ans1 = 0
for i in range(N-1):
    ans1 += abs(D[i+1]-D[i])

A.sort(reverse=True)
D = deque()
for i in range(N):
    if i%4==0:
        D.append(A[i//2])
    elif i%4==1:
        D.appendleft(A[-1-(i-1)//2])
    elif i%4==2:
        D.appendleft(A[i//2])
    else:
        D.append(A[-1-(i-1)//2])
ans2 = 0
for i in range(N-1):
    ans2 += abs(D[i+1]-D[i])
    
print(max(ans1,ans2))

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

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


A.sort()

def calc(A):
    ans = 0
    tmp1 = A[0]
    tmp2 = A[0]

    count = 1
    flag = True
    i = 1
    j = 1
    while True:
        if flag:
            if tmp1 > tmp2:
                tmp1, tmp2 = tmp2, tmp1
        else:
            if tmp1 < tmp2:
                tmp1, tmp2 = tmp2, tmp1


        if count == N:
            break
        if flag:
            ans += abs(tmp1 - A[-i])
            tmp1 = A[-i]
            i += 1
        else:
            ans += abs(tmp1 - A[j])
            tmp1 = A[j]
            j += 1

        count += 1

        if count == N:
            break
        if flag:
            ans += abs(tmp2 - A[-i])
            tmp2 = A[-i]
            i += 1
        else:
            ans += abs(tmp2 - A[j])
            tmp2 = A[j]
            j += 1
        
        count += 1

        flag = not flag
        
    return ans


print (max(calc(A[::-1]), calc(A)))

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
a=[int(input())for _ in range(n)]
a.sort()
ans1=0
ans2=0
if n%2:
    for i in range(n):
        if i<n//2:
            ans1-=a[i]*2
        elif i<n//2+2:
            ans1+=a[i]
        else:
            ans1+=a[i]*2
    for i in range(n):
        if i<(n-2)//2:
            ans2-=a[i]*2
        elif i<(n-2)//2+2:
            ans2-=a[i]
        else:
            ans2+=a[i]*2
    print(max(ans1,ans2))

else:
    for i in range(n):
        if i<(n-2)//2:
            ans1-=a[i]*2
        elif i<(n-2)//2+1:
            ans1-=a[i]
        elif i<(n-2)//2+2:
            ans1+=a[i]
        else:
            ans1+=a[i]*2
    print(ans1)

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

N, *A = map(int, read().split())

A.sort()
A = deque(A)
a = deque()
side = True
a.append(A.popleft())

while A:
    if side:
        a.append(A.pop())
        if A:
            a.appendleft(A.pop())
        side = False
    else:
        a.append(A.popleft())
        if A:
            a.appendleft(A.popleft())
        side = True

if side:
    tmp = a.popleft()
else:
    tmp = a.pop()

if abs(tmp - a[0]) <= abs(tmp - a[-1]):
    a.append(tmp)
else:
    a.appendleft(tmp)

if not side:
    tmp = a.popleft()
else:
    tmp = a.pop()

if abs(tmp - a[0]) <= abs(tmp - a[-1]):
    a.append(tmp)
else:
    a.appendleft(tmp)

answer = 0
a = list(a)
for i, j in zip(a, a[1:]):
    answer += abs(i - j)

print(answer)

Solution (Python):
from collections import deque
N = int(input())
A = deque(sorted([int(input()) for _ in range(N)]))
B = deque([])
B.append(A.popleft())
cnt = 0
while A:
    a0 = A[0]
    a1 = A[-1]
    b0 = B[0]
    b1 = B[-1]
    c00 = abs(a0-b0)
    c01 = abs(a0-b1)
    c10 = abs(a1-b0)
    c11 = abs(a1-b1)
    cmax = max(c00,c01,c10,c11)
    if cmax == c00:
        B.appendleft(A.popleft())
    elif cmax == c01:
        B.append(A.popleft())
    elif cmax == c10:
        B.appendleft(A.pop())
    else:
        B.append(A.pop())
    cnt += cmax
print(cnt)

Solution (Python):
from collections import deque
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
x = deque(a)
y = deque(a)


def align(a, fromLeft=1):
    if fromLeft:
        p = a.popleft()
    else:
        p = a.pop()
    q = p

    res = 0
    fromLeft = 1 - fromLeft
    while a:
        p1 = a.popleft() if fromLeft else a.pop()
        if a:
            q1 = a.popleft() if fromLeft else a.pop()
            res += abs(p - p1) + abs(q - q1)
            p = p1
            q = q1
        else:
            res += max(abs(p - p1), abs(q - p1))
        fromLeft = 1 - fromLeft
    return res


ans = max(align(x, 1), align(y, 0))
print(ans)

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


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

    import collections
    q = collections.deque(A)

    p = collections.deque()
    p.append(q.pop())
    ans = 0
    while q:
        q1, q2 = q[0], q[-1]
        p1, p2 = p[0], p[-1]
        a = abs(q1 - p1)
        b = abs(q1 - p2)
        c = abs(q2 - p1)
        d = abs(q2 - p2)
        ma = max(a, b, c, d)
        ans += ma
        if ma == a:
            p.appendleft(q.popleft())
        elif ma == b:
            p.append(q.popleft())
        elif ma == c:
            p.appendleft(q.pop())
        elif ma == d:
            p.append(q.pop())
    print(ans)


if __name__ == '__main__':
    main()

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



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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools

n=int(input())
a=list(int(input()) for i in range(n))
b=[]
a.sort()
ans=0

if n%2==1:
    x=2*sum(a[n//2+1:])-2*sum(a[:n//2+1])+sum(a[n//2-1:n//2+1])
    y=2*sum(a[n//2:])-sum(a[n//2:n//2+2])-2*sum(a[:n//2])
    print(max(x,y))

else:
    x=2*sum(a[n//2:])-(a[n//2]) -2*sum(a[:n//2])+a[n//2-1]
    print(x)

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

A.sort()

ret1 = 0
i, j = 1, len(A) - 1
e1, e2 = A[0], A[0]
mode = 0

while i <= j :
    if i == j :
        ret1 += max(abs(e1-A[i]), abs(e2-A[i]))
        i += 1
    else :
        if mode == 0 :
            ret1 += abs(e1-A[j]) + abs(e2-A[j-1])
            e1, e2 = A[j], A[j-1]
            j -= 2
        else :
            ret1 += abs(e1-A[i]) + abs(e2-A[i+1])
            e1, e2 = A[i], A[i+1]
            i += 2
            
        mode ^= 1
        
ret2 = 0
i, j = 0, len(A) - 2
e1, e2 = A[-1], A[-1]
mode = 1

while i <= j :
    if i == j :
        ret2 += max(abs(e1-A[i]), abs(e2-A[i]))
        i += 1
    else :
        if mode == 0 :
            ret2 += abs(e1-A[j]) + abs(e2-A[j-1])
            e1, e2 = A[j], A[j-1]
            j -= 2
        else :
            ret2 += abs(e1-A[i]) + abs(e2-A[i+1])
            e1, e2 = A[i], A[i+1]
            i += 2
            
        mode ^= 1
        
print(max(ret1, ret2))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    b = IR(n)
    b.sort()
    a = deque(b)
    q = deque([a.pop()])
    n -= 1
    for i in range(n):
        if i&2:
            ai = a.pop()
        else:
            ai = a.popleft()
        x = q[0]
        y = q[-1]
        if i&1:
            q.append(ai)
        else:
            q.appendleft(ai)
    ans = 0
    for i in range(n):
        ans += abs(q[i+1]-q[i])
    a = deque(b)
    q = deque([a.popleft()])
    for i in range(n):
        if i&2:
            ai = a.popleft()
        else:
            ai = a.pop()
        if i&1:
            q.append(ai)
        else:
            q.appendleft(ai)
    ans2 = 0
    for i in range(n):
        ans2 += abs(q[i+1]-q[i])
    print(max(ans,ans2))
    return



if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    b = IR(n)
    b.sort()
    a = deque(b)
    q = deque([a.pop()])
    n -= 1
    for i in range(n):
        if i&1:
            ai = a.pop()
        else:
            ai = a.popleft()
        x = q[0]
        y = q[-1]
        if abs(x-ai) < abs(y-ai):
            q.append(ai)
        else:
            q.appendleft(ai)
    ans = 0
    for i in range(n):
        ans += abs(q[i+1]-q[i])
    a = deque(b)
    q = deque([a.popleft()])
    for i in range(n):
        if i&1:
            ai = a.popleft()
        else:
            ai = a.pop()
        x = q[0]
        y = q[-1]
        if abs(x-ai) < abs(y-ai):
            q.append(ai)
        else:
            q.appendleft(ai)
    ans2 = 0
    for i in range(n):
        ans2 += abs(q[i+1]-q[i])
    a = deque(b)
    q = deque([a.pop()])
    for i in range(n):
        if i&2:
            ai = a.pop()
        else:
            ai = a.popleft()
        x = q[0]
        y = q[-1]
        if abs(x-ai) < abs(y-ai):
            q.append(ai)
        else:
            q.appendleft(ai)
    ans3 = 0
    for i in range(n):
        ans3 += abs(q[i+1]-q[i])
    a = deque(b)
    q = deque([a.popleft()])
    for i in range(n):
        if i&2:
            ai = a.popleft()
        else:
            ai = a.pop()
        x = q[0]
        y = q[-1]
        if abs(x-ai) < abs(y-ai):
            q.append(ai)
        else:
            q.appendleft(ai)
    ans4 = 0
    for i in range(n):
        ans4 += abs(q[i+1]-q[i])
    print(max(ans,ans2,ans3,ans4))
    return



if __name__ == "__main__":
    solve()

Solution (Python):
import numpy as np
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
if N % 2 == 0:
  up = [-1,1]
  down = [-1,1]
else:
  up = [-1,-1]
  down = [1,1]
for i in range(1,N-1):
  if i % 2 == 0:
    up.append(-2)
    down.append(2)
  else:
    up.append(2)
    down.append(-2)
up.sort()
down.sort()
up = np.array(up)
down = np.array(down)
print(max(np.sum(up * A),np.sum(down * A)))

Solution (Python):

import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = 0
count = 0
n=int(input())
A=[int(input()) for i in range(n)]
A.sort()
if n%2==1:
    if A[n//2]-A[n//2-1]<=A[n//2+1]-A[n//2]:
        A.insert(0,A[n//2+1])
    else:
        A.append(A[n//2])
    n+=1
tmp=A[n//2]
for i in range(n//2):
    ans+=abs(tmp-A[i+n//2])
    tmp = A[i+n//2]
    
    ans+=abs(tmp-A[i])
    tmp=A[i]
    
print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, A):
    b = deque()
    A.sort()
    for i in range(N//2):
        if i % 2 == 0:
            b.appendleft(A[i])
            b.append(A[N-i-1])
        else:
            b.append(A[i])
            b.appendleft(A[N-i-1])
    if N % 2 !=  0:
        a = A[N//2]
        l = b[0]
        r = b[-1]
        if abs(a-l) > abs(a-r):
            b.appendleft(a)
        else:
            b.append(a)
    
    ans = 0
    for i in range(N-1):
        ans += abs(b[i]-b[i+1])
        
    return ans


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
a.sort()
ans1=ans2=0
p=q=a[n//2]
if n%2==0:
	for i in range(n//2-1):
		ans1+=abs(p-a[i])
		p=a[i]
		ans1+=abs(p-a[-i-1])
		p=a[-i-1]
	ans1+=abs(p-a[n//2-1])
	print(ans1)
else:
	for i in range(n//2):
		ans1+=abs(p-a[i])
		p=a[i]
		ans1+=abs(p-a[-i-1])
		p=a[-i-1]
		ans2+=abs(q-a[-i-1])
		q=a[-i-1]
		ans2+=abs(q-a[i])
		q=a[i]
	print(max(ans1,ans2))

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
answer = 0
if N%2 == 0:
    lower = A[:N//2]
    upper = A[N//2:]
    x = 2 * sum(upper) - upper[0]
    y = 2 * sum(lower) - lower[-1]
    answer = x - y
else:
    mid = A[N//2]
    lower = A[:N//2]
    upper = A[N//2 + 1:]
    r1 = 2 * sum(upper) - mid - (2 * sum(lower) - lower[-1])
    r2 = 2 * sum(upper) - upper[0] + mid - 2 * sum(lower)
    answer = max(r1, r2)
print(answer)

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
from collections import deque
A.sort()
q=deque(A)
q2=deque()
q2.append(q.popleft())
k=N-1
while(k>0):
  if len(q)>0:
    q2.appendleft(q.pop())
    k-=1
  if len(q)>0:
    q2.append(q.pop())
    k-=1
  if len(q)>0:
    q2.appendleft(q.popleft())
    k-=1
  if len(q)>0:
    q2.append(q.popleft())
    k-=1
  if len(q)==0:
    break
prev=q2.popleft()
ans=0
for i in range(N-1):
  now=q2.popleft()
  ans+=abs(now-prev)
  prev=now

q=deque(A)
q2=deque()
q2.append(q.pop())
k=N-1
while(k>0):
  if len(q)>0:
    q2.appendleft(q.popleft())
    k-=1
  if len(q)>0:
    q2.append(q.popleft())
    k-=1
  if len(q)>0:
    q2.append(q.pop())
    k-=1
  if len(q)>0:
    q2.appendleft(q.pop())
    k-=1
  if len(q)==0:
    break
prev=q2.popleft()
tmp=0
for i in range(N-1):
  now=q2.popleft()
  tmp+=abs(now-prev)
  prev=now  
  
print(max(ans,tmp))

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


value=0
B,C=A[0],A[0]
i=1
z=0

while N-1>z:

    if z%4==0:
        value+=A[-i]-B
        B=A[-i]
    if z%4==1:
        value+=A[-i-1]-C
        C=A[-i-1]
    if z%4==2:
        value+=B-A[i]
        B=A[i]
    if z%4==3:
        value+=C-A[i+1]
        C=A[i+1]
        i+=2
    
    z+=1
value1=value
value=0
B,C=A[-1],A[-1]
i=0
z=0
while N-1>z:

    if z%4==0:
        value+=B-A[i]
        B=A[i]

    if z%4==1:
        value+=C-A[i+1]
        C=A[i+1]

    if z%4==2:
        value+=A[-i-2]-B
        B=A[-i-2]
    if z%4==3:
        value+=A[-i-3]-C
        C=A[-i-3]
        i+=2
    
    z+=1
value2=value
print(max(value1,value2))

Solution (Python):
n=int(input())
l=[]
for i in range(n):
    l.append(int(input()))
l.sort()
if n%2==0:
    s=l[:n//2]
    b=l[n//2:]
    ans=0
    for i in range(n-1):
        if i%2==0:
            ans+=b[i//2]-s[i//2]
        else:
            ans+=b[(i+1)//2]-s[i//2]
    print(ans)
else:
    s=l[:n//2]
    b=l[n//2+1:]+[l[n//2]]
    ans1=0
    for i in range(n-1):
        if i%2==0:
            ans1+=b[i//2]-s[i//2]
        else:
            ans1+=b[(i+1)//2]-s[i//2]
    t=[l[(n//2)]]+l[:n//2]
    c=l[n//2+1:]
    ans2=0
    for i in range(n-1):
        if i%2==0:
            ans2+=c[i//2]-t[i//2]
        else:
            ans2+=c[i//2]-t[(i+1)//2]
    print(max(ans1,ans2))

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
a=[int(input())for _ in range(n)]
a.sort()
ans1=0
ans2=0
if n%2:
    for i in range(n):
        if i<n//2:
            ans1-=a[i]*2
        elif i<n//2+2:
            ans1+=a[i]
        else:
            ans1+=a[i]*2
    for i in range(n):
        if i<(n-2)//2:
            ans2-=a[i]*2
        elif i<(n-2)//2+2:
            ans2-=a[i]
        else:
            ans2+=a[i]*2
    print(max(ans1,ans2))

else:
    for i in range(n):
        if i<(n-2)//2:
            ans1-=a[i]*2
        elif i<(n-2)//2+1:
            ans1-=a[i]
        elif i<(n-2)//2+2:
            ans1+=a[i]
        else:
            ans1+=a[i]*2
    print(ans1)

Solution (Python):
n = int(input())
a_ls = []
for i in range(n):
    a_ls.append(int(input()))
a_ls.sort()
flg = n % 2 == 1
if flg:
    first = a_ls[:n//2]
    center = a_ls[n//2]
    second = a_ls[n//2 + 1:] + [center]
    best = 0
    for ind in range(n//2):
        best += abs(second[ind] - first[ind]) + abs(second[ind + 1] - first[ind])
    center = a_ls[n // 2]
    first = [center] + a_ls[:n // 2]
    second = a_ls[n // 2 + 1:]
    score = 0
    for ind in range(n // 2):
        score += abs(second[ind] - first[ind]) + abs(second[ind] - first[ind+1])
    if best < score:
        best = score
else:
    first = a_ls[:n // 2]
    second = a_ls[n // 2:]
    best = 0
    for ind, (i, j) in enumerate(zip(first, second)):
        if ind > 0:
            best += abs(j - last_i)
        best += abs(j - i)
        last_i = i
print(best)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
ans = 0
if N % 2 == 0:
  l = A[:N//2]
  h = A[N//2:]
  for i,j in zip(l, h):
    ans += (j - i) * 2 
  ans = ans - h[0] + l[-1]
else:
  l = A[:N//2]
  h = A[N//2+1:]
  m = A[N//2]
  for i,j in zip(l, h):
    ans += (j - i) * 2 
  ans = max(ans - h[0] + m, ans + l[-1] - m)
print(ans)

Solution (Python):
n = int(input())
a = sorted([int(input()) for i in range(n)])
b = list(a[::-1])



def f(A):
    l = r = A.pop(0)

    ans = 0

    for i in range(len(A)//2):
        if i % 2 == 0:
            ans += abs(l - A[-1]); l = A.pop(-1);
            ans += abs(r - A[-1]); r = A.pop(-1);
        else:
            ans += abs(l - A[0]); l = A.pop(0);
            ans += abs(r - A[0]); r = A.pop(0);
    if (A):
        ans += abs(l - A[0])

    return ans


print(max(f(a), f(b)))

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

for i in range(N):
    A.append(int(input()))

A = sorted(A)

B = [0] * N
m = int(N/2)
B[m] = A[0]

si = 1
bi = 0
ci = 1

for i in range(1, N):
    si *= -1
    ii = int(i/2 + 0.5)

    if i % 4 == 1 or i % 4 == 2:
        B[m+si*ii] = A[N-bi-1]
        bi += 1
    if i % 4 == 3 or i % 4 == 0:
        B[m+si*ii] = A[ci]
        ci += 1

C = [0] * N
m = int(N/2)
C[m] = A[N-1]

si = 1
bi = 1
ci = 0

for i in range(1, N):
    si *= -1
    ii = int(i/2 + 0.5)

    if i % 4 == 1 or i % 4 == 2:
        C[m+si*ii] = A[ci]
        ci += 1
    if i % 4 == 3 or i % 4 == 0:
        C[m+si*ii] = A[N-bi-1]
        bi += 1

cntB = 0
cntC = 0
for i in range(N-1):
    cntB += abs(B[i] - B[i+1])
    cntC += abs(C[i] - C[i+1])


print(max(cntB, cntC))

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

A.sort()

k1=[]
if N%2==1:
    k1.extend([1,1])
    k1.extend([-2]*(N//2))
    k1.extend([2]*(N-N//2-2))
    k1.sort()
    sum1=0
    sum2=0
    for i in range(N):
        sum1+=A[i]*k1[i]
        sum2+=(-1)*A[i]*k1[-1-i]
    print(max(sum1,sum2))
else:
    k1.extend([-1,1])
    k1.extend([-2]*((N-2)//2))
    k1.extend([2]*((N-2)//2))
    k1.sort()
    sum1=0
    sum2=0
    for i in range(N):
        sum1+=A[i]*k1[i]
        sum2+=(-1)*A[i]*k1[-1-i]
    print(max(sum1,sum2))

Solution (Python):
import collections

N=int(input())

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

A.sort()

ans=[A[0],A[-1]]
ans=collections.deque(ans)
l=1
r=-2
n=[0]*4
ansn=abs(A[0]-A[-1])
for i in range(N-2):
    n[0]=abs(A[l]-ans[0])
    n[1]=abs(A[l]-ans[-1])
    n[2]=abs(A[r]-ans[0])
    n[3]=abs(A[r]-ans[-1])
    if n[0]==max(n):
        ansn+=n[0]
        ans.appendleft(A[l])
        l+=1
    elif n[1]==max(n):
        ansn+=n[1]
        ans.append(A[l])
        l+=1
    elif n[2]==max(n):
        ansn+=n[2]
        ans.appendleft(A[r])
        r-=1
    elif n[3]==max(n):
        ansn+=n[3]
        ans.append(A[r])
        r-=1

print(ansn)

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

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

A.sort()

ansl=A[0]
ansr=A[-1]
l=1
r=-2
n=[0]*4
ansn=abs(A[0]-A[-1])
for i in range(N-2):
    n[0]=abs(A[l]-ansl)
    n[1]=abs(A[l]-ansr)
    n[2]=abs(A[r]-ansl)
    n[3]=abs(A[r]-ansr)
    if n[0]==max(n):
        ansn+=n[0]
        ansl=A[l]
        l+=1
    elif n[1]==max(n):
        ansn+=n[1]
        ansr=A[l]
        l+=1
    elif n[2]==max(n):
        ansn+=n[2]
        ansl=A[r]
        r-=1
    elif n[3]==max(n):
        ansn+=n[3]
        ansr=A[r]
        r-=1

print(ansn)

Solution (Python):
n=int(input())
l=[]
for i in range(n):
  l.append(int(input()))
l1=sorted(l)
if n%2==0:
  k=n//2
  sum=0
  for i in range(0,k):
    sum-=2*l1[i]
  for i in range(k,n):
    sum+=2*l1[i]
  sum-=l1[k]
  sum+=l1[k-1]
  print(sum)
else:
  k=n//2
  sum=0
  for i in range(k,n):
    sum+=2*l1[i]
  for i in range(k):
    sum-=2*l1[i]
  sum-=l1[k]
  sum-=l1[k+1]
  sum1=0
  for i in range(k+1,n):
    sum1+=2*l1[i]
  for i in range(k+1):
    sum1-=2*l1[i]
  sum1+=l1[k]
  sum1+=l1[k-1]
  print(max(sum,sum1))

Solution (Python):

n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())
a.sort(reverse=True)
ook = []
tii = []
for i in range(0, n//2):
    ook.append(a[i])
for i in range(n//2, n):
    tii.append(a[i])
if n % 2 == 0:
    ans = 2 * (sum(ook) - sum(tii)) - (ook[-1] - tii[0])
    print(ans)
else:
    tmp = tii.pop(0)
    tmp1 = 2 * (sum(ook) - sum(tii)) + (tii[0]) - tmp
    tmp2 = 2 * (sum(ook) - sum(tii)) + tmp - ook[-1]
    print(max(tmp1, tmp2))

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def main():
    n = int(input().strip())
    a = [0] * n
    for i in range(n):
        a[i] = int(input().strip())
    a = sorted(a)
    ans = 0
    if n % 2 == 0:
        kei1 = sorted([1, -1] + [-2] * ((n-2)//2) + [2] * ((n-2)//2))
        for i in range(n):
            ans += a[i] * kei1[i]
    else:
        kei1 = sorted([-1] * 2 + [2] * (n//2) + [-2] * (n//2 - 1))
        kei2 = sorted([1] * 2 + [2] * (n//2-1) + [-2] * (n//2))
        ans2 = 0
        for i in range(n):
            ans += a[i] * kei1[i]
            ans2 += a[i] * kei2[i]
        ans = max(ans, ans2)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import*
n,*a=map(int,open(0).read().split())
def f(a):
  a=deque(a)
  deq=deque([a.popleft()])
  for i in range(n-1):
    if i%4==0:
      deq.appendleft(a.pop())
    elif i%4==1:
      deq.append(a.pop())
    elif i%4==2:
      deq.appendleft(a.popleft())
    else:
      deq.append(a.popleft())
  l=list(deq)
  return sum(abs(i-j)for i,j in zip(l,l[1:]))
s=sorted(a)
print(max(f(s),f(s[::-1])))

Solution (Python):
from collections import deque

N = int(input())
A = []
B = []

for i in range(N):

    a = int(input())

    A.append(a)

A.sort()

now = A.pop(0)
L = now
R = now
ans = 0
Lind = 0
Rind = -1

for i in range(N-1):

    if abs(L-A[Lind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(L-A[Lind])
        L = A[Lind]
        Lind += 1

    elif abs(L-A[Rind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])): 
        ans += abs(L-A[Rind])
        L = A[Rind]
        Rind -= 1

    elif abs(R-A[Lind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(R-A[Lind])
        R = A[Lind]
        Lind += 1

    elif abs(R-A[Rind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(R-A[Rind])
        R = A[Rind]
        Rind -= 1

    else:
        print ("eeror")

    

print (ans)

Solution (Python):
N = int(input())
A = list(int(input())for i in range(N))
A.sort()
L = []
R = []
for i in range(N):
    if i%2 == 0:
        L.append(A[i//2])
        R.append(A[-(i//2)-1])
    else:
        L.append(A[-(i//2)-1])
        R.append(A[i//2])
saL,saR = [],[]
for i in range(N):
    saL.append(abs(L[i]-L[i-1]))
    saR.append(abs(R[i]-R[i-1]))
print(max(sum(saL)-min(saL),sum(saR)-min(saR)))

Solution (Python):
from copy import copy
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
A1 = copy(A)
A2 = copy(A)
B1 = []
B2 = []
i=0
while A1 and A2:
    if i%2 == 0:
        B1.append(A1.pop(0))
        B2.append(A2.pop(-1))
    else:
        B1.append(A1.pop(-1))
        B2.append(A2.pop(0))
    i += 1
B1.append(B1[0])
B2.append(B2[0])
C1 = [abs(B1[i+1]-B1[i]) for i in range(len(B1)-1)]
C2 = [abs(B2[i+1]-B2[i]) for i in range(len(B2)-1)]
print(max(sum(C1)-min(C1),sum(C2)-min(C2)))

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

A_sorted = sorted(A,reverse=True)

if N%2:
  a1=2*(sum(A_sorted[:N//2])-sum(A_sorted[N//2:]))+A_sorted[N//2]+A_sorted[N//2+1]
  a2=2*(sum(A_sorted[:N//2+1])-sum(A_sorted[N//2+1:]))-A_sorted[N//2]-A_sorted[N//2-1]
  print(max(a1,a2))
else:
  print(2*(sum(A_sorted[:N//2])-sum(A_sorted[N//2:]))-A_sorted[N//2-1]+A_sorted[N//2])

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

ans = -1

if n % 2 == 1:
    sum2 = 0
    sum1 = 0
    for i in range(n):
        if n // 2 - 1 <= i <= n // 2:
            sum1 -= a[i]
        elif i < n // 2:
            sum2 -= a[i]
        else:
            sum2 += a[i]
    ans = max(ans, sum2 * 2 + sum1)

    a.reverse()
    sum2 = 0
    sum1 = 0
    for i in range(n):
        if n // 2 - 1 <= i <= n // 2:
            sum1 += a[i]
        elif i < n // 2:
            sum2 += a[i]
        else:
            sum2 -= a[i]
    ans = max(ans, sum2 * 2 + sum1)
else:
    Sum = 0
    for i in range(n):
        if i == n // 2 - 1:
            Sum -= a[i]
        elif i == n // 2:
            Sum += a[i]
        elif i < n // 2:
            Sum -= a[i] * 2
        else:
            Sum += a[i] * 2
    ans = max(ans, Sum)
    
    
print(ans)

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

a = sorted(a)


s_a = a[0:n//2]
l_a = a[n//2:]

if len(s_a) == len(l_a):
    print(2*sum(l_a) - l_a[0] - 2*sum(s_a) + s_a[-1])

else:
    tmp_ans1 = 2*sum(l_a) - l_a[0] - l_a[1] - 2*sum(s_a)    
    s_a = a[0:n//2+1]
    l_a = a[n//2+1:]
    tmp_ans2 = 2*sum(l_a) - 2*sum(s_a) + s_a[-2] + s_a[-1]
    print(max(tmp_ans1, tmp_ans2))

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

lis=sorted(lists)
if n%2==0:
    sig=sum(lis)
    left=sum(lis[:n//2])
    print(2*sig-4*left+lis[n//2-1]-lis[n//2])
if n%2!=0:
    sig=sum(lis)
    print(max(2*sig-4*sum(lis[:(n-1)//2])-lis[(n-1)//2]-lis[(n+1)//2], 2*sig-4*sum(lis[:(n+1)//2])+lis[(n-1)//2]+lis[(n-3)//2]))

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

if N%2 == 0:
  S = A[:N//2]
  L = A[N//2:]
  ans = 2*sum(L)-L[0]-2*sum(S)+S[-1]
else:
  S1 = A[:N//2]
  L1 = A[N//2:]
  S2 = A[:N//2+1]
  L2 = A[N//2+1:]
  ans1 = 2*sum(L1)-L1[0]-L1[1]-2*sum(S1)
  ans2 = 2*sum(L2)-2*sum(S2)+S2[-1]+S2[-2]
  ans = max(ans1,ans2)
print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
if n % 2 == 0:
    half_n = n // 2
    pre = a[:half_n]
    post = a[half_n:]
    print((sum(post) * 2 - post[0]) - (sum(pre) * 2 - pre[-1]))
else:
    half_n = n // 2
    pre1 = a[:half_n]
    post1 = a[half_n:]
    pre2 = a[:half_n+1]
    post2 = a[half_n+1:]
    diff1 = (sum(post1) * 2 - post1[0] - post1[1]) - sum(pre1) * 2
    diff2 = sum(post2) * 2 - (sum(pre2) * 2 - pre2[-1] - pre2[-2])
    print(max(diff1, diff2))