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())
alst = [int(input()) for _ in range(n)]
alst.sort()
if n % 2 == 0:
    mid = n // 2
    ans = sum(alst[mid + 1:]) * 2 + alst[mid] - sum(alst[:mid - 1]) * 2 - alst[mid - 1]
else:
    mid = n // 2
    ans1 = sum(alst[mid + 1:]) * 2 - sum(alst[:mid - 1]) * 2 - alst[mid - 1] - alst[mid]
    ans2 = sum(alst[mid + 2:]) * 2 - sum(alst[:mid]) * 2 + alst[mid + 1] + alst[mid]
    ans = max(ans1, ans2)
    
print(ans)

Solution (Python):
N = int(input())
A = sorted(int(input()) for TN in range(0,N))
if N%2==0:
    S = A[:(N//2)]
    B = A[(N//2):]
    SS = -2*sum(S)+S[-1]
    BS = 2*sum(B)-B[0]
    PT = SS+BS
    print(PT)
else:
    S = A[:(N//2)]
    B = A[(N//2):]
    SS1 = -2*sum(S)
    BS1 = 2*sum(B)-B[0]-B[1]
    PT1 = SS1+BS1
    
    SS2 = -2*sum(S)+S[-1]
    BS2 = 2*sum(B)-3*B[0]
    PT2 = SS2+BS2
    print(max(PT1,PT2))

Solution (Python):
import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec1 = [0] * N
    vec2 = [0] * N
    for i in range(N - 1):
        if i % 2 == 0:
            vec1[i] += 1
            vec1[i + 1] -= 1
            vec2[i] -= 1
            vec2[i + 1] += 1
        else:
            vec1[i] -= 1
            vec1[i + 1] += 1
            vec2[i] += 1
            vec2[i + 1] -= 1

    vec1.sort()
    vec2.sort()

    ans1 = ans2 = 0
    for a, v1, v2 in zip(A, vec1, vec2):
        ans1 += a * v1
        ans2 += a * v2

    print(max(ans1, ans2))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline

def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    A.sort()
    if N%2 == 0:
        Bp = A[N//2:]
        Bm = A[:N//2]
        ans = 2*sum(Bp) - min(Bp) - 2*sum(Bm) + max(Bm)
    else:
        Bp = A[N//2+1:]
        Bm = A[:N//2+1]
        cnt = 2*sum(Bp) - 2*sum(Bm) + sum(Bm[-2:])

        Cp = A[N//2:]
        Cm = A[:N//2]
        ans = max(cnt, 2*sum(Cp) - sum(Cp[:2]) - 2*sum(Cm))

    print(ans)
        
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n = int(input())
D = []
for _ in range(n):
  D.append(int(input()))
D.sort()
A = deque(D)
B = deque()
B.append(A.popleft())

maxflag = 0
while True:
  if len(A) == 0:
    break
  if len(A) == 1:
    a = A.pop()
    B.appendleft(a)
    break
  if maxflag % 2 == 0:
    a = A.pop()
    b = A.pop()
  else:
    a = A.popleft()
    b = A.popleft()
  B.appendleft(a)
  B.append(b)
  maxflag += 1
ans = 0
for i in range(len(B)-1):
  ans += abs(B[i] - B [i+1])

A = deque(D)
B = deque()
B.append(A.pop())

maxflag = 1
while True:
  if len(A) == 0:
    break
  if len(A) == 1:
    a = A.pop()
    B.appendleft(a)
    break
  if maxflag % 2 == 0:
    a = A.pop()
    b = A.pop()
  else:
    a = A.popleft()
    b = A.popleft()
  B.appendleft(a)
  B.append(b)
  maxflag += 1
ans2 = 0
for i in range(len(B)-1):
  ans2 += abs(B[i] - B [i+1])
print(max(ans, ans2))

Solution (Python):

def resolve():
    
    
    
    
    

    def f(arr):
        res = 0
        for i in range(N - 1):
            res += abs(arr[i + 1] - arr[i])
        return res

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

    
    

    mid = N // 2
    ans = 0
    if N % 2 == 0:
        low, high = A[:mid], A[mid:]
        B = []
        for i in range(mid):
            B.append(high[i])
            B.append(low[i])
        ans = f(B)

    else:
        res1 = 0
        low, high = A[:mid], A[mid + 1:]
        B = []
        for i in range(mid):
            B.append(high[i])
            B.append(low[i])
        
        B.append(A[mid])
        res1 = f(B)

        
        B = [A[mid]] + B[:-1]

        ans = max(res1, f(B))

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):

def resolve():
    
    
    
    
    

    

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

    
    
    res1 = 0
    left = 0
    right = N - 1
    i = 0
    while (right - left) > 1:
        res1 += abs(A[right] - A[left])
        if i % 2 == 0:
            right -= 1
        else:
            left += 1
        i += 1
    if N % 2 == 1:
        
        res1 += max(abs(A[N - 1] - A[right]), abs(A[left] - A[right]))
    else:
        res1 += max(abs(A[N - 1] - A[left]), abs(A[right] - A[left]))

    
    
    res2 = 0
    left = 0
    right = N - 1
    i = 0
    while (right - left) > 1:
        res2 += abs(A[right] - A[left])
        if i % 2 == 0:
            left += 1
        else:
            right -= 1
        i += 1
    if N % 2 == 1:
        
        res2 += max(abs(A[0] - A[left]), abs(A[left] - A[right]))
    else:
        res2 += max(abs(A[0] - A[right]), abs(A[right] - A[left]))

    ans = max(res1, res2)
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
ans = 0
left, right = 1, 0
el, er = A[0], A[0] 
while left + right < N:
    a = abs(A[left]-el)
    b = abs(A[left]-er)
    c = abs(A[-right-1]-el)
    d = abs(A[-right-1]-er)
    m = max(a, b, c, d)
    if m == a:
        ans += a
        el = A[left]
        left += 1
    elif m == b:
        ans += b
        er = A[left]
        left += 1
    elif m == c:
        ans += c
        el = A[-right-1]
        right += 1
    else:
        ans += d
        er = A[-right-1]
        right += 1

print(ans)

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

A = sorted(A)

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

Solution (Python):






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





A.sort()
ans = 0
if N%2 == 0:
    ans = 2*(sum(A[N//2:]) - sum(A[:N//2])) + A[N//2 - 1] - A[N//2]
else:
    ans = 2*(sum(A[N//2 + 1:]) - sum(A[:N//2]))
    ans -= min(A[N//2 + 1] - A[N//2], A[N//2] - A[N//2 - 1])
print(ans)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)



    

    
    
    
def main():
    N, *h = map(int, read().split())
    h.sort()
    hh = h.copy()

    ans = 0
    t = h.pop(-1)
    t1 = t
    pm = 0
    while 1:
        t2 = h.pop(pm)
        ans += abs(t - t2)
        if len(h) == 0:
            break
        t = t2

        t3 = h.pop(pm)
        ans += abs(t1 - t3)
        if len(h) == 0:
            break
        t1 = t3

        if pm==0:
            pm = -1
        else:
            pm = 0

    ans1 = 0
    h = hh
    t = h.pop(0)
    t1 = t
    pm = -1

    while 1:
        t2 = h.pop(pm)
        ans1 += abs(t - t2)
        if len(h) == 0:
            break
        t = t2

        t3 = h.pop(pm)
        ans1 += abs(t1 - t3)
        if len(h) == 0:
            break
        t1 = t3
        if pm == 0:
            pm = -1
        else:
            pm = 0

    print(max(ans, ans1))

if __name__ == "__main__":
    main()

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

for i in range(N):
    v = int(input())
    h.append(v)
h.sort()
hh = h.copy()

ans = 0
t = h.pop(-1)
t1 = t
pm = 0
while 1:
    t2 = h.pop(pm)
    ans += abs(t - t2)
    if len(h) == 0:
        break
    t = t2

    t3 = h.pop(pm)
    ans += abs(t1 - t3)
    if len(h) == 0:
        break
    t1 = t3

    if pm==0:
        pm = -1
    else:
        pm = 0

ans1 = 0
h = hh
t = h.pop(0)
t1 = t
pm = -1

while 1:
    t2 = h.pop(pm)
    ans1 += abs(t - t2)
    if len(h) == 0:
        break
    t = t2

    t3 = h.pop(pm)
    ans1 += abs(t1 - t3)
    if len(h) == 0:
        break
    t1 = t3
    if pm == 0:
        pm = -1
    else:
        pm = 0


print(max(ans, ans1))

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

A = [int(input()) for _ in range(N)]
A.sort()
B = A[::-1]

l1 = []
l2 = []
for i in range((N + int(N % 2 == 0)) // 2):
    l1.append(A[i])
    l1.append(B[i])
    l2.append(B[i])
    l2.append(A[i])

a, b = 0, 0
for i in range(N - int(N % 2 == 1) - 1):
    a += abs(l1[i] - l1[i + 1])
    b += abs(l2[i] - l2[i + 1])



if N % 2 == 0:
    a -= abs(l1[-1] - l1[-2])
    b -= abs(l2[-1] - l2[-2])
    a += max(abs(l1[0] - l1[-1]), abs(l1[-2] - l1[-1]))
    b += max(abs(l2[0] - l2[-1]), abs(l2[-2] - l2[-1]))
else:
    a += max(abs(l1[0] - A[(N - 1) // 2]), abs(l1[-1] - A[(N - 1) // 2]))
    b += max(abs(l2[0] - A[(N - 1) // 2]), abs(l2[-1] - A[(N - 1) // 2]))
res = max(a, b)



print(res)

Solution (Python):
N, *A = map(int, open(0).read().split())
M = N // 2
A.sort()
ans = 0
if N % 2:
    for i in range(1, M):
        ans += A[i + M + 1] - A[i - 1]
        ans += A[i + M + 1] - A[i]
    ans += A[M + 1] - A[0]
    ans = max(A[M + 1] - A[M] + ans, ans + A[M] - A[M - 1])
else:
    ans += A[M] - A[0]
    for i in range(1, M):
        ans += A[i + M] - A[i - 1]
        ans += A[i + M] - A[i]
print(ans)

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

A.sort()

if n%2 == 0:
    ans = A[n//2]-A[n//2-1]
    m = A[n//2]-A[n//2-1]
    for i in range(n):
        if i == n//2-1 or i == n//2:
            continue
        else:
            if i <= n//2:
                ans += m-2*A[i]
            else:
                ans += 2*A[i]-m
else:
    m = A[n//2]
    ans1 = m-A[n//2-1]
    for i in range(n):
        if i == n//2-1 or i == n//2:
            continue
        else:
            ans1 += 2*abs(A[i]-m)
    m = A[n//2]
    ans2 = A[n//2+1]-m
    for i in range(n):
        if i == n//2+1 or i == n//2:
            continue
        else:
            ans2 += 2*abs(A[i]-m)
    ans = max(ans1, ans2)
print(ans)

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

A.sort()

if n%2 == 0:
    ans = A[n//2]-A[n//2-1]
    m = A[n//2]-A[n//2-1]
    for i in range(n):
        if i == n//2-1 or i == n//2:
            continue
        else:
            if i <= n//2:
                ans += m-2*A[i]
            else:
                ans += 2*A[i]-m
else:
    m = A[n//2]
    ans1 = m-A[n//2-1]
    for i in range(n):
        if i == n//2-1 or i == n//2:
            continue
        else:
            ans1 += 2*abs(A[i]-m)
    m = A[n//2]
    ans2 = A[n//2+1]-m
    for i in range(n):
        if i == n//2+1 or i == n//2:
            continue
        else:
            ans2 += 2*abs(A[i]-m)
    ans = max(ans1, ans2)
print(ans)

Solution (Python):
N = int(input())
A = sorted([int(input()) for _ in range(N)])
if N%2==0:
    B = A[:N//2]
    C = A[N//2:]
    C = C[::-1]
    D1 = []
    D2 = []
    for i in range(N//2-1):
        D1.append(B[i])
        D1.append(C[i])
        D2.append(C[i])
        D2.append(B[i])
    D1.append(B[-1])
    D1.insert(0,C[-1])
    D2.append(C[-1])
    D2.insert(0,B[-1])
    cnt1 = 0
    cnt2 = 0
    for i in range(1,N):
        cnt1 += abs(D1[i]-D1[i-1])
        cnt2 += abs(D2[i]-D2[i-1])
    print(max(cnt1,cnt2))
else:
    B = A[:N//2]
    C = A[N//2+1:]
    C = C[::-1]
    D1 = []
    D2 = []
    for i in range(N//2):
        D1.append(B[i])
        D1.append(C[i])
        D2.append(C[i])
        D2.append(B[i])
    cnt1 = 0
    cnt2 = 0
    for i in range(1,N-1):
        cnt1 += abs(D1[i]-D1[i-1])
        cnt2 += abs(D2[i]-D2[i-1])
    cnt1 += max(A[N//2]-D1[0],D1[-1]-A[N//2])
    cnt2 += max(D2[0]-A[N//2],A[N//2]-D2[-1])
    print(max(cnt1,cnt2))

Solution (Python):

import sys
def main(N, A):
    A.sort()
    B = [A[i // 2] if i & 1 == 0 else A[-1 - i // 2] for i in range(N)]
    C = [A[i // 2] if i & 1 == 1 else A[-1 - i // 2] for i in range(N)]

    print(max(f(B), f(C)))

def f(L):
    res = 0
    for i in range(len(L) - 1):
        res += abs(L[i] - L[i - 1])
    return res

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    main(N, A)

Solution (Python):
import sys, math
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

N = ii()
A = [ii() for i in range(N)]

A.sort()
u1, u2 = [], []
l1, l2 = [], []
for i in range(N):
    if i < N//2:
        l1.append(A[i])
    else:
        u1.append(A[i])

    if i < (N+1)//2:
        l2.append(A[i])
    else:
        u2.append(A[i])

if N%2:
    ans = max(
        (2*sum(u1)-u1[0]-u1[1]) - 2*sum(l1),
        2*sum(u2) - (2*sum(l2)-l2[-1]-l2[-2])
    )
else:
    ans = (2*sum(u1)-u1[0]) - (2*sum(l1)-l1[-1])

print(ans)

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


def f(A, N):
    l = [0]*N
    a = (N+1)//2

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

    if N%2==1:
        l[-1], l[2] = l[2], l[-1]

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

    return s


print(max(f(A, N), f(list(reversed(A)), N)))

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

A.sort()
n = N//2
if N%2 != 0:
    ans1,ans2,ans = 0,0,0
    ar1,ar2 = A[:n],A[n+1:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    ar.append(A[n])
    for i in range(N-1):
        ans1 += abs(ar[i]-ar[i+1])
    ar = [A[n]]+ar[:-1]
    for i in range(N-1):
        ans2 += abs(ar[i]-ar[i+1])
    ans = max(ans1,ans2)
else:
    ans = 0
    ar1,ar2 = A[:n],A[n:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    for i in range(N-1):
        ans += abs(ar[i]-ar[i+1])
 
print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
A = sorted(A)
B = list(reversed(A))
ans = -1


if(N % 2 == 0):
    k = N//2
    typeN = -(2*sum(A[:k])+A[k]) + (2*sum(B[:k])+B[k])
    ans = typeN
else:
    k = N//2
    typeW = (2*sum(B[:k-1])+B[k-1]+B[k]) - (2*sum(A[:k]))
    typeM = (2*sum(B[:k])) - (2*sum(A[:k-1])+A[k-1]+A[k])
    ans = max(typeW,typeM)
print(ans)

Solution (Python):
n=int(input())
a=[]
for i in range(n):
    aa=int(input())
    a.append(aa)
from collections import deque
a.sort()
a=deque(a)

omi=a.popleft()
oma=a.pop()
ans=abs(oma-omi)
ret=True

while len(a)>1:
    mi=a.popleft()
    ma=a.pop()

    if ret:
        mi,ma=ma,mi

    ans+=abs(omi-mi)+abs(oma-ma)
    omi,oma=mi,ma
    ret = not ret

if len(a)==1:
    aa=a.pop()
    ans+=max(abs(omi-aa),abs(oma-aa))

print(ans)

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

A.sort()

l = 0
r = N-1
p = []
ans = 0
while l < r:
    p.append(A[r])
    p.append(A[l])
    r -= 1
    l += 1
if N % 2 == 1:
    p.append(A[r])

p.append(p[0])
q = []
for i in range(len(p)-1):
    q.append(abs(p[i] - p[i+1]))

ans = sum(q)-min(q)

l = 0
r = N-1
p = []
while l < r:
    p.append(A[l])
    p.append(A[r])
    r -= 1
    l += 1
if N % 2 == 1:
    p.append(A[r])

p.append(p[0])
q = []
for i in range(len(p)-1):
    q.append(abs(p[i] - p[i+1]))

print(max(ans,sum(q)-min(q)))

Solution (Python):
from collections import deque
from copy import deepcopy
n=int(input())
a=sorted([int(input()) for _ in range(n)])
c=deepcopy(a)

a=deque(a)
b=deque([a.popleft()])

i=0
while a:
    if (i//2)%2==0:
        if i%2==0:
            deque.append(b,a.pop())
        else:
            deque.appendleft(b,a.pop())
    else:
        if i%2==0:
            deque.append(b,a.popleft())
        else:
            deque.appendleft(b,a.popleft())
    
    i+=1
ans=0
for i in range(1,n):
    ans+=abs(b[i]-b[i-1])

c=deque(c)
b=deque([c.pop()])

i=0
while c:
    if (i//2)%2==0:
        if i%2==0:
            deque.append(b,c.popleft())
        else:
            deque.appendleft(b,c.popleft())
    else:
        if i%2==0:
            deque.append(b,c.pop())
        else:
            deque.appendleft(b,c.pop())
    
    i+=1
cnt=0
for i in range(1,n):
    cnt+=abs(b[i]-b[i-1])
ans=max(ans,cnt)

print(ans)

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

from collections import*
A.sort()
ans1=deque()
ans1.append(A[0])
i=j=1
while i<=N-j:
    if i<=N-j:
        ans1.append(A[-j])
        j+=1
    if i<=N-j:
        ans1.appendleft(A[-j])
        j+=1
    if i<=N-j:
        ans1.append(A[i])
        i+=1
    if i<=N-j:
        ans1.appendleft(A[i])
        i+=1
ans1=list(ans1)
ans1=sum(abs(x-y)for x,y in zip(ans1,ans1[1:]))

A=A[::-1]
ans2=deque()
ans2.append(A[0])
i=j=1
while i<=N-j:
    if i<=N-j:
        ans2.append(A[-j])
        j+=1
    if i<=N-j:
        ans2.appendleft(A[-j])
        j+=1
    if i<=N-j:
        ans2.append(A[i])
        i+=1
    if i<=N-j:
        ans2.appendleft(A[i])
        i+=1
ans2=list(ans2)
ans2=sum(abs(x-y)for x,y in zip(ans2,ans2[1:]))

print(max(ans1,ans2))

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)









INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def run():
    N, *A = map(int, read().split())
    A.sort()
    if not N % 2:
        Al = A[:N // 2]
        Ah = A[N // 2:]
        ans = 0
        ans += 2 * sum(Ah)
        ans -= Ah[0]
        ans -= 2 * sum(Al)
        ans += Al[-1]
        print(ans)

    else:
        
        Al = A[:N // 2]
        Ah = A[N // 2:]
        
        ans1 = 0
        ans1 += 2 * sum(Ah)
        ans1 -= sum(Ah[:2])
        ans1 -= sum(Al) * 2

        
        Al = A[:N // 2 + 1]
        Ah = A[N // 2 + 1:]
        
        ans2 = 0
        ans2 += 2 * sum(Ah)
        ans2 -= sum(Al) * 2
        ans2 += sum(Al[-2:])
        print(max(ans1, ans2))

if __name__ == "__main__":
    run()

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

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

Solution (Python):
N=int(input())
M=N//2
l=[int(input()) for i in range(N)]
l.sort()
if N%2==0:
   print(-2*sum(l[0:M-1])-l[M-1]+l[M]+2*sum(l[M+1:]))
else:
   pt1=-2*sum(l[:M-1])-l[M-1]-l[M] +2*sum(l[M+1:])
   pt2=-2*sum(l[:M]) +l[M] + l[M+1] +2*sum(l[M+2:])
   print(max(pt1,pt2))

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

ans = 0
d = deque(sorted(A))
while len(d) > 3:
    ans += 2*(deque.pop(d)-deque.popleft(d))
if len(d) == 2:
    ans += deque.pop(d)-deque.popleft(d)
else:
    a, b, c = d
    ans += max(b+c-2*a, -a-b+2*c) 
    
print(ans)

Solution (Python):
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    
    
    
    
    
    
    
    if N % 2 == 1:
        n = N // 2
        ans_1 = 0
        for i, a in enumerate(A):
            coef = 2
            if i < n:  
                coef = -2
            elif i < n + 2:  
                coef = 1
            ans_1 += coef * a
        ans_2 = 0
        for i, a in enumerate(A):
            coef = 2
            if i < n - 1:  
                coef = -2
            elif i < n + 1:  
                coef = -1
            ans_2 += coef * a
        print(max(ans_1, ans_2))
    
    
    
    
    else:
        n = N // 2
        ans = 0
        for i, a in enumerate(A):
            coef = 2
            if i < n - 1:  
                coef = -2
            elif i < n:  
                coef = -1
            elif i < n + 1:  
                coef = 1
            ans += coef * a
        print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
from collections import deque
import copy
import sys
sys.setrecursionlimit(50000)
N = int(input())
d_1, d_2 = deque([]), deque([])
l = []
for i in range(N):
  l.append(int(input()))
  
l.sort()
l_1, l_2 = copy.copy(l), copy.copy(l)
d_1.append(max(l))
d_2.append(min(l))
l_1.pop()
l_2.pop(0)

def main1(d, l):
  d.appendleft(l[0])
  l.pop(0)
  if l == []:
    return d
  d.append(l[0])
  l.pop(0)
  if l == []:
    return d
  d.appendleft(l[-1])
  l.pop()
  if l == []:
    return d
  d.append(l[-1])
  l.pop()
  if l == []:
    return d
  else:
    return main1(d, l)
  
def main2(d, l):
  d.appendleft(l[-1])
  l.pop()
  if l == []:
    return d
  d.append(l[-1])
  l.pop()
  if l == []:
    return d
  d.appendleft(l[0])
  l.pop(0)
  if l == []:
    return d
  d.append(l[0])
  l.pop(0)
  if l == []:
    return d
  else:
    return main2(d, l)
  
x, y = 0, 0
a = main1(d_1, l_1)
b = main2(d_2, l_2)
for i in range(N-1):
  x += abs(a[i+1]-a[i])
  y += abs(b[i+1]-b[i])
print(max(x, y))

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

Solution (Python):

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


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


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def func1(A):
    ans = 0
    N = len(A)
    m, p = [], []
    for i in range(N):
        if i < N // 2:
            m.append(A[i])
        else:
            p.append(A[i])

    ans -= sum(m) * 2
    ans += sum(p) * 2

    if N % 2 == 0:
        ans += m[-1]
        ans -= p[0]
    else:
        ans -= p[0]
        ans -= p[1]

    return ans


def func2(A):
    ans = 0
    N = len(A)
    m, p = [], []
    for i in range(N):
        if i < N // 2 + 1:
            m.append(A[i])
        else:
            p.append(A[i])

    ans -= sum(m) * 2
    ans += sum(p) * 2

    if N % 2 == 0:
        ans += m[-1]
        ans -= p[0]
    else:
        ans += m[-1]
        ans += m[-2]

    return ans


def solve(A):
    return max(func1(A[:]), func2(A[:]))


def check(A):
    ans = 0
    for p in permutations(A):
        tmp = 0
        for i in range(1, len(p)):
            tmp += abs(p[i] - p[i - 1])

        ans = max(ans, tmp)
    return ans


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

    if N < 5:
        print(check(A))
    else:
        print(solve(A))


if __name__ == '__main__':
    main()

Solution (Python):


import sys

from collections import deque


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = []
    for _ in range(n):
        A.append(input_int())
    A = sorted(A)
    dq = deque(A)
    ans = 0

    
    left = dq.popleft()
    right = dq.pop()
    ans = abs(right - left)

    while dq:
        l = dq[0]
        r = dq[-1]
        if abs(left - l) == max(abs(left - l), abs(right - l), abs(left - r), abs(right - r)):
            ans += abs(left - l)
            left = l
            dq.popleft()
        elif abs(left - r) == max(abs(left - l), abs(right - l), abs(left - r), abs(right - r)):
            ans += abs(left - r)
            left = r
            dq.pop()
        elif abs(right - l) == max(abs(left - l), abs(right - l), abs(left - r), abs(right - r)):
            ans += abs(right - l)
            right = l
            dq.popleft()
        elif abs(right - r) == max(abs(left - l), abs(right - l), abs(left - r), abs(right - r)):
            ans += abs(right - r)
            right = r
            dq.pop()

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
work = []
ans = 0
if N % 2 == 1:
    before = A[:N // 2]
    after = A[N // 2 + 1:]
    median = A[N // 2]
    for i in range(N // 2):
        work.append(after[i])
        work.append(before[i])
    work.append(median)
    tmp1 = 0
    tmp2 = 0
    for i in range(N - 1):
        tmp1 += abs(work[i] - work[i + 1])
    t = work.pop()
    work.insert(0, t)
    for i in range(N - 1):
        tmp2 += abs(work[i] - work[i + 1])
    ans = max(tmp1, tmp2)

else:
    before = A[:N // 2]
    after = A[N // 2:]
    for i in range(N // 2):
        work.append(after[i])
        work.append(before[i])
    for i in range(N - 1):
        ans += abs(work[i] - work[i + 1])
print(ans)

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

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

A.sort()

half = math.floor(n/2)
if n ==2:
    print(A[1]-A[0])
else:
    half_A = A[half]
    dif = A[half+1] - half_A*2 +A[half-1]
    if (n%2 == 1) & (dif>0):
        total = sum(A[half+1:])*2 - sum(A[:half-1])*2 -A[half] - A[half-1]
    elif (n % 2 == 1) & (dif<=0):
        total = sum(A[half+2:])*2 - sum(A[:half])*2 + A[half] + A[half+1]
    else:
        total = sum(A[half+1:])*2 - sum(A[:half-1])*2 -A[half-1] + A[half]
    
    print(total)

Solution (Python):

N = int(input())
A = [0]+[int(input()) for _ in range(N)]
A = sorted(A)
ans = 0
if N%2==0:
    i = 1
    while i<N//2:
        ans -= 2*A[i]
        i += 1
    ans -= A[i]
    i += 1
    ans += A[i]
    i += 1
    while i<=N:
        ans += 2*A[i]
        i += 1
else:
    i = 1
    while i<N//2:
        ans -= 2*A[i]
        i += 1
    ans -= A[i]
    i += 1
    ans -= A[i]
    i += 1
    while i<=N:
        ans += 2*A[i]
        i += 1
    tmp = 0
    A = [0]+sorted(A[1:], reverse=True)
    i = 1
    while i<N//2:
        tmp += 2*A[i]
        i += 1
    tmp += A[i]
    i += 1
    tmp += A[i]
    i += 1
    while i<=N:
        tmp -= 2*A[i]
        i += 1
    ans = max(ans,tmp)
print(ans)

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    A.sort()

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    if N == 2:
        print(abs(A[0] - A[1]))
        return

    A.sort()

    q = collections.deque(A)

    ans = 0
    i = 0
    c = [q.popleft(), q.pop()]
    ans += abs(c[0] - c[1])
    while q:
        if len(q) >= 2:
            a = q.popleft()
            b = q.pop()
            al = abs(a - c[0])
            ar = abs(a - c[1])
            bl = abs(b - c[0])
            br = abs(b - c[1])
            ma = max([al, ar, bl, br])
            ans += ma
            if ma == al:
                c[0] = a
                q.append(b)
            elif ma == ar:
                c[1] = a
                q.append(b)
            elif ma == bl:
                c[0] = b
                q.appendleft(a)
            else:
                c[1] = b
                q.appendleft(a)
        else:
            a = q.pop()
            ans += max(abs(c[0] - a), abs(c[1] - a))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque

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

Q=deque(range(1,N))
R=deque([0])
for i in range((N-1)//2):
    if i%2:
        x=Q.popleft()
        y=Q.popleft()
    else:
        x=Q.pop()
        y=Q.pop()

    R.appendleft(x)
    R.append(y)

if Q:
    x=Q.pop()
    R.appendleft(x)

X=[0]*N
Y=[0]*N
for i in range(N):
    X[i]=A[R[i]]
    Y[i]=A[-(R[i]+1)]

alpha=0
beta=0

for i in range(N-1):
    alpha+=abs(X[i+1]-X[i])
    beta +=abs(Y[i+1]-Y[i])
print(max(alpha,beta))

Solution (Python):
n = int(input())
A = [int(input()) for _ in range(n)]
A = sorted(A,reverse=True)

ans = 0
if n%2 == 1:
  i = -1
  for i in range((n-2)//2):
    ans += A[i]*2
    ans -= A[-i-1]*2    
  ans += A[i+1]
  ans += A[i+2]
  ans -= A[i+3] *2
  
  tmp = 0
  for i in range((n-2)//2):
    tmp += A[i]*2
    tmp -= A[-i-1]*2    
  tmp += A[i+1] *2
  tmp -= A[i+2]
  tmp -= A[i+3]
  ans = max(ans,tmp)
  
else:
  i = -1
  for i in range((n-2)//2):
    ans += 2*A[i]
    ans -= 2*A[-i-1]      
  ans += A[i+1]
  ans -= A[i+2]
  
print(ans)

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

from collections import deque
from typing import Deque

A.sort()

DL = Deque(A)
DS = Deque(A)

LL = [0 for _ in range(N)]
LS = [0 for _ in range(N)]


if N % 2 == 0:

    for i in range(1, N, 2):
        LS[i] = DS.popleft()
        LL[i] = DL.pop()
    for j in range(0, N, 2):
        LS[j] = DS.popleft()
        LL[j] = DL.pop()

else:
    for i in range(1, N):
        if i % 2 == 1:
            LS[i] = DS.pop()
            LL[i] = DL.popleft()
        else:
            LS[i] = DS.popleft()
            LL[i] = DL.pop()

    LS[0] = DS.pop()
    LL[0] = DL.pop()

ansS = 0
ansL = 0
for i in range(1, N, 2):
    if i == N - 1:
        ansS += abs(LS[i] - LS[i-1])
        ansL += abs(LL[i] - LL[i-1])
    else:
        ansS += abs(LS[i] - LS[i-1])
        ansS += abs(LS[i] - LS[i+1])

        ansL += abs(LL[i] - LL[i-1])
        ansL += abs(LL[i] - LL[i+1])

print(max(ansS, ansL))

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

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