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 deque

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

if N == 2:
    print(abs(A_list[0] - A_list[1]))
    exit()

if N == 3:
    a0,a1,a2 = A_list
    print(max(abs(a0-a1) + abs(a1-a2),abs(a1-a2) + abs(a2-a0) ,abs(a0-a2) + abs(a0-a1)))
    exit()
    
q = deque(A_list)
res_q = deque([q.popleft(), q.pop()])
l = res_q[0]
r = res_q[-1]

v1 = v2 =0

v1 = q.popleft()
v2 = q.pop()
res = abs(l-r)
for _ in range(2,N-2):
    diff_l1 = abs(l-v1)
    diff_l2 = abs(l-v2)
    diff_r1 = abs(r-v1)
    diff_r2 = abs(r-v2)
    max_diff = max(diff_l1,diff_l2, diff_r1, diff_r2)
    
    res += max_diff
    if diff_l1 == max_diff:
        l = v1
        v1 = q.popleft()
    elif diff_l2 == max_diff:
        l = v2
        v2 = q.pop()
    elif diff_r1 == max_diff:
        r = v1
        v1 = q.popleft()
    else:
        r = v2
        v2 = q.pop()


diff_list = [abs(l-v1) + abs(v1-v2),
            abs(l-v1) + abs(r-v2),
            abs(l-v2) + abs(v1-v2),
            abs(l-v2) + abs(r-v1),
            abs(r-v1) + abs(l-v2),
            abs(r-v1) + abs(v1-v2),
            abs(r-v2) + abs(l-v1),
            abs(r-v2) + abs(v1-v2)]
res += max(diff_list)

print(res)

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

Solution (Python):
n = int(input())
arr = [int(input()) for x in range(n)]

arr.sort()

med = n // 2


if n % 2 == 0:
    ans = 2 * sum(arr[med + 1:]) - 2 * sum(arr[:med - 1]) + arr[med] - arr[med - 1]

else:
    ans1 = 2 * sum(arr[med + 1:]) - 2 * sum(arr[:med - 1]) - arr[med - 1] - arr[med]
    ans2 = 2 * sum(arr[med + 2:]) - 2 * sum(arr[:med]) + arr[med + 1] + arr[med]
    ans = max(ans1, ans2)

print(ans)

Solution (Python):
from collections import deque

n=int(input())
a = []

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

a.sort()

a=deque(a)

mid = a[(n-1)//2]
midi = abs(a[(n-1)//2-1] - mid)
mida = abs(a[(n-1)//2+1] - mid)

rev = False
omi = a[0]
oma = a[-1]

ans = abs(oma - omi)
for i in range(len(a)//2):
    mi = a.popleft()
    ma = a.pop()

    if rev:
        q = mi
        mi = ma
        ma = q

    ans+=abs(mi - omi)+abs(ma - oma)

    omi = mi
    oma = ma
    rev = not rev

if len(a)==1:
    ans+=max(midi,mida)

print(ans)

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

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

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

main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N = getN()
A = sorted(getArray(N))
A = deque(A)
ans_list = deque([])

cnt = 0
for i in range(N // 2):

    m = A.popleft()
    if cnt % 2 == 0:
        ans_list.append(m)
    else:
        ans_list.appendleft(m)

    m = A.pop()
    if cnt % 2 == 0:
        ans_list.appendleft(m)
    else:
        ans_list.append(m)
    cnt += 1

if N % 2 == 1:
    m = A.pop()
    opt1 = abs(ans_list[0] - m)
    opt2 = abs(ans_list[-1] - m)

    if opt1 >= opt2:
        ans_list.appendleft(m)
    else:
        ans_list.append(m)

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

Solution (Python):
n = int(input())
a = sorted(int(input()) for _ in range(n))
m = n // 2
if n % 2 == 0:
    ans = (sum(a[m:]) - sum(a[:m])) * 2 - a[m] + a[m-1]
    print(ans)
else:
    ans1 = (sum(a[m+1:]) - sum(a[:m])) * 2 - a[m] + a[m-1]
    ans2 = (sum(a[m+1:]) - sum(a[:m])) * 2 - a[m+1] + a[m]
    print(max(ans1, ans2))

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

if n%2==0:
    front=a[:n//2]
    rear=a[n//2:]
    f1=deque(front)
    f2=deque(front)
    r1=deque(rear)
    r2=deque(rear)
    ans1=0
    ans2=0
    for i in range(n):
        
        if i==0:
            last1=f1.pop()
            last2=r2.popleft()
        elif i%2==1:
            now1=r1.pop()
            now2=f2.popleft()
            ans1+=abs(last1-now1)
            ans2+=abs(last2-now2)
            last1=now1
            last2=now2
        elif i%2==0:
            now1=f1.popleft()
            now2=r2.pop()
            ans1+=abs(last1-now1)
            ans2+=abs(last2-now2)
            last1=now1
            last2=now2
    print(max(ans1,ans2))
else:
    med=a[n//2]
    front=a[:n//2]
    rear=a[n//2+1:]
    f1=deque(front)
    f2=deque(front)
    r1=deque(rear)
    r2=deque(rear)
    ans1=0
    ans2=0
    for i in range(n):
        
        if i==0:
            last1=med
            last2=med
        elif i%2==1:
            now1=r1.pop()
            now2=f2.popleft()
            ans1+=abs(last1-now1)
            ans2+=abs(last2-now2)
            last1=now1
            last2=now2
        elif i%2==0:
            now1=f1.popleft()
            now2=r2.pop()
            ans1+=abs(last1-now1)
            ans2+=abs(last2-now2)
            last1=now1
            last2=now2
    print(max(ans1,ans2))

Solution (Python):
from collections import deque
n = int(input())
A = []
for _ in range(n):
    A.append(int(input()))
if n == 2:
    print(abs(A[1]-A[0]))
    exit()
A.sort()
s = sum(A)
if n % 2 == 1:
    small = 0
    for i in range(n//2):
        small += A[i]
    big = s - small
    ans1 = 2*big-2*small-A[n//2]-A[n//2+1]
    small += A[n//2]
    big = s-small
    ans2 = 2*big -2*small+A[n//2]+A[n//2-1]
    print(max(ans1,ans2))
else:
    small = 0
    for i in range(n//2):
        small += A[i]
    big = s -small
    ans1 = 2*big -2*small + A[n//2-1]-A[n//2]
    small += A[n//2]
    big = s -small
    ans2 = 2*big-2*small+A[n//2]-A[n//2+1]
    print(max(ans1,ans2))

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

A.sort()

arr = []
arr.append(A[0])
arr.append(A[-1])
Atop = 1
Abtm = len(A) - 2
ans = arr[-1]-arr[0]
for i in range(len(A)-2):
    (Ai, ai) = (Atop, 0)
    if abs(A[Atop]-arr[-1]) > abs(A[Ai]-arr[ai]):
        (Ai, ai) = (Atop, -1)
    if abs(A[Abtm]-arr[0]) > abs(A[Ai]-arr[ai]):
        (Ai, ai) = (Abtm, 0)
    if abs(A[Abtm]-arr[-1]) > abs(A[Ai]-arr[ai]):
        (Ai, ai) = (Abtm, -1)

    
    
    ans += abs(A[Ai]-arr[ai])
    if ai == -1:
        arr[-1] = A[Ai]
    else:
        arr[0] = A[Ai]

    if Ai == Atop:
        Atop += 1
    else:
        Abtm -= 1


print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = [0] * N
    for n in range(N):
        A[n] = int(input())
    
    A.sort()
    ans1 = sum([-2*a for a in A[:N//2+N%2]]) + sum([2*a for a in A[N//2+N%2:]])
    if N % 2:
        ans1 += A[N//2-1]
        ans1 += A[N//2]
    else:
        ans1 += A[N//2-1]
        ans1 -= A[N//2]

    ans2 = sum([-2*a for a in A[:N//2]]) + sum([2*a for a in A[N//2:]])
    if N % 2:
        ans2 -= A[N//2]
        ans2 -= A[N//2+1]
    else:
        ans2 -= A[N//2]
        ans2 += A[N//2-1]

    print(max(ans1, ans2))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import copy
N = int(input())
A = deque(sorted([int(input()) for i in range(N)]))
B = copy.copy(A)
ans = deque([A.popleft()])
while A:
    if A:
        ans.appendleft(A.pop())
    if A:
        ans.append(A.pop())
    if A:
        ans.appendleft(A.popleft())
    if A:
        ans.append(A.popleft())
res_1 = 0
ans = list(ans)
for i in range(N - 1):
    res_1 += abs(ans[i] - ans[i + 1])
ans = deque([B.pop()])
while B:
    if B:
        ans.appendleft(B.popleft())
    if B:
        ans.append(B.popleft())
    if B:
        ans.appendleft(B.pop())
    if B:
        ans.append(B.pop())
res_2 = 0
ans = list(ans)
for i in range(N - 1):
    res_2 += abs(ans[i] - ans[i + 1])
print(max(res_1, res_2))

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

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

r_asc = sorted(r)
r_desc = sorted(r, reverse=True)
row = []
row2 = []

for i in range(N):
    if i % 2 == 0:
        row.append(r_asc[i//2])
        row2.append(r_desc[i//2])
    else:
        row.append(r_desc[i//2])
        row2.append(r_asc[i//2])
row3 = [row[-1]] + row[:-1]
row4 = [row2[-1]] + row2[:-1]
row_diff = [abs(row[i] - row[i-1]) for i in range(1, N)]
row2_diff = [abs(row2[i] - row2[i-1]) for i in range(1, N)]
row3_diff = [abs(row3[i] - row3[i-1]) for i in range(1, N)]
row4_diff = [abs(row4[i] - row4[i-1]) for i in range(1, N)]
print(max(sum(row_diff), sum(row2_diff), sum(row3_diff), sum(row4_diff)))

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


n = int(input())
L = [int(input()) for _ in range(n)]
L.sort()
n_2 =n // 2

ans = 0
if n % 2 == 1:
    ans = 2*sum(L[n_2+1:])-2*sum(L[:n_2-1])-L[n_2-1]-L[n_2]
    ans_2 = 2*sum(L[n_2+2:])-2*sum(L[:n_2])+L[n_2+1]+L[n_2]
    ans = max(ans,ans_2)
else:
    ans = 2*sum(L[n_2+1:])-2*sum(L[:n_2-1])+L[n_2]-L[n_2-1]
    

print(ans)

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

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

rlt = 0

if len(As) % 2 == 1:
  tmp1 = 0
  tmp2 = 0
  b = len(As)//2
  for i in As[:b]:
    tmp1 -= 2*i
  for i in As[b:]:
    tmp1 += 2*i
  tmp1 -= As[b]
  tmp1 -= As[b+1]
  
  for i in As[:b+1]:
    tmp2 -= 2*i
  for i in As[b+1:]:
    tmp2 += 2*i
  tmp2 += As[b]
  tmp2 += As[b-1]
  if tmp1 > tmp2:
    rlt = tmp1
  else:
    rlt = tmp2

else:
  b = len(As)//2
  for i in As[:b]:
    rlt -= 2*i
  for i in As[b:]:
    rlt += 2*i
  rlt += As[b-1]
  rlt -= As[b]
  
print(rlt)

Solution (Python):
n=int(input())
l=sorted([int(input())for i in range(n)],reverse=1)
if n%2:
    print(max(2*sum(l[:n//2-1])+l[n//2-1]+l[n//2]-2*sum(l[n//2+1:]),2*sum(l[:n//2])-sum(l[n//2:n//2+2])-2*sum(l[n//2+2:])))
else:
    o=-1
    print(2*sum(l[:n//2-1])+l[n//2+o]-l[n//2+1+o]-2*sum(l[o+n//2+2:]))

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

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

A.sort(reverse=True)

s=0
if n%2==0:
    s=2*sum(A[0:(n//2-1)])+A[n//2-1]-A[n//2]-2*sum(A[n//2+1:n])
else:
    s1=2*sum(A[0:n//2-1])+A[n//2-1]+A[n//2]-2*sum(A[n//2+1:n])
    s2=2*sum(A[0:n//2])-A[n//2]-A[n//2+1]-2*sum(A[n//2+2:n])
    s=max(s1,s2)

print(s)

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = sorted([Z() for _ in range(N)])
    used = [0] * (N)
    output1 = output2 = 0

    i1 = i2 = 0
    j1, j2 = N-1, N-2
    f1 = f2 = True
    used[i1], used[i2], used[j1], used[j2] = 1, 1, 1, 1

    while f1 or f2:
        if f1: output1 += (A[j1]-A[i1])
        if f2: output1 += (A[j2]-A[i2])

        while used[i1]:
            if i1 == N-1:
                f1 = False
                break
            i1 += 1
        used[i1] = 1

        while used[i2]:
            if i2 == N-1:
                f2 = False
                break
            i2 += 1
        used[i2] = 1

        if f1: output1 += (A[j1]-A[i1])
        if f2: output1 += (A[j2]-A[i2])

        while used[j1]:
            if j1 == 0:
                f1 = False
                break
            j1 -= 1
        used[j1] = 1
        while used[j2]:
            if j2 == 0:
                f2 = False
                break
            j2 -= 1
        used[j2] = 1

    i1, i2 = 0, 1
    j1 = j2 = N-1
    f1 = f2 = True
    used = [0] * (N)
    used[i1], used[i2], used[j1], used[j2] = 1, 1, 1, 1

    while f1 or f2:
        if f1: output2 += (A[j1]-A[i1])
        if f2: output2 += (A[j2]-A[i2])

        while used[j1]:
            if j1 == 0:
                f1 = False
                break
            j1 -= 1
        used[j1] = 1
        while used[j2]:
            if j2 == 0:
                f2 = False
                break
            j2 -= 1
        used[j2] = 1

        if f1: output2 += (A[j1]-A[i1])
        if f2: output2 += (A[j2]-A[i2])

        while used[i1]:
            if i1 == N-1:
                f1 = False
                break
            i1 += 1
        used[i1] = 1

        while used[i2]:
            if i2 == N-1:
                f2 = False
                break
            i2 += 1
        used[i2] = 1


    print(max(output1, output2))

    return

if __name__ == '__main__':
    main()

Solution (Python):
def point(arr):
    res=0
    for i in range(1,N):
        res+=abs(arr[i]-arr[i-1])
    return res
def merge(li_1,li_2):
    arr=[]
    for i in range(N):
        if not i%2:
            arr.append(li_2[i//2])
        else:
            arr.append(li_1[i//2])
    return arr

N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
if not N%2:
    ans=0
    l,r=A[:N//2],A[N//2:]
    print(point(merge(l,r)))
else:
    ans=-1
    li=[]
    l,r=A[:N//2],A[N//2:]
    r[1],r[-1]=r[-1],r[1]
    ans=max(ans,point(merge(l,r)))
    li=[]
    l,r=A[:N//2+1],A[N//2+1:]
    l[0],l[-2]=l[-2],l[0]
    ans=max(ans,point(merge(r,l)))
    print(ans)

Solution (Python):
from collections import deque

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

a.sort()
def calc(m):
    if m == 1:
        dqa = deque(a[1:])
        dq = deque([a[0]])
        cnt = 0
    else: 
        dqa = deque(a[:N-1])
        dq = deque([a[-1]])
        cnt = 2

    while len(dq) < N:
        if cnt == 0:
            q = dqa.pop()
            dq.append(q)
        elif cnt == 1:
            q = dqa.pop()
            dq.appendleft(q)
        elif cnt == 2:
            q = dqa.popleft()
            dq.append(q)
        else:
            q = dqa.popleft()
            dq.appendleft(q)
            cnt = -1
        cnt += 1

    ans = 0
    for i in range(1, N):
        ans += abs(dq[i] - dq[i-1])
    return ans
        
print(max(calc(0), calc(1)))

Solution (Python):
N=int(input())
a = [int(input()) for _ in range(N)]
b = [0]*N

if N%2==1:
  
  a.sort()
  m = N//2
  L,R = m,m
  b[m]=a[-1]
  for i in range(m):
    L -= 1
    R += 1
    if i%2==0:
      b[L]=a[i]
      b[R]=a[i+1]
    else:
      b[L]=a[-2-(i-1)]
      b[R]=a[-3-(i-1)]
  ans1=0
  for i in range(1,N):
    ans1 += abs(b[i]-b[i-1])
  
  
  
  a.sort()
  m = N//2
  L,R = m,m
  b[m]=a[0]
  for i in range(m):
    L -= 1
    R += 1
    if i%2==0:
      b[L]=a[-1-i]
      b[R]=a[-2-i]
    else:
      b[L]=a[(i-1)+1]
      b[R]=a[(i-1)+2]
  ans2=0
  for i in range(1,N):
    ans2 += abs(b[i]-b[i-1])
  ans=max(ans1,ans2)
  
  print(ans)

else:
  a.sort()
  m = N//2
  L,R = m-1,m
  b[L]=a[0]
  b[R]=a[-1]
  
  for i in range(m-1):
    L -= 1
    R += 1
    if i%2==0:
      b[L]=a[-2-i]
      b[R]=a[i+1]
    else:
      b[L]=a[i+1]
      b[R]=a[-2-i]
  ans=0
  for i in range(1,N):
    ans += abs(b[i]-b[i-1])
  
  print(ans)

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

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

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

if n % 2 == 0:
    res = 0
    for i in range(n // 2 - 1):
        res += a[i] * 2
    res += a[n // 2 - 1]
    res -= a[n // 2]
    for i in range(n // 2 + 1, n):
        res -= a[i] * 2
    print(res)
else:
    res1 = 0
    for i in range(n // 2 - 1):
        res1 += a[i] * 2
    res1 += a[n // 2 - 1] + a[n // 2]
    for i in range(n // 2 + 1, n):
        res1 -= a[i] * 2

    res2 = 0
    for i in range(n // 2):
        res2 += a[i] * 2
    res2 -= a[n // 2] + a[n // 2 + 1]
    for i in range(n // 2 + 2, n):
        res2 -= a[i] * 2
    print(max(res1, res2))

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

if n % 2 == 0:
    res = 0
    for i in range(n//2-1):
        res += a[i] * 2
    res += a[n//2-1]
    res -= a[n//2]
    for i in range(n//2+1, n):
        res -= a[i] * 2
    print(res)
else:
    res1 = 0
    for i in range(n//2-1):
        res1 += a[i] * 2
    res1 += a[n//2-1] + a[n//2]
    for i in range(n//2+1, n):
        res1 -= a[i] * 2
    
    res2 = 0
    for i in range(n//2):
        res2 += a[i] * 2
    res2 -= a[n//2] + a[n//2+1]
    for i in range(n//2+2, n):
        res2 -= a[i] * 2
    print(max(res1, res2))

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

Solution (Python):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





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

    a.sort()

    ans1 = []
    ans2 = []
    if not n % 2:
        small = a[:n // 2]
        large = a[n // 2:]
        for i in range(n // 2):
            ans2.append(large[i])
            ans2.append(small[i])

        tmp_ans = 0
        for i in range(1, n):
            tmp_ans += abs(ans2[i - 1] - ans2[i])

        print(tmp_ans)

    else:
        small1 = a[:n // 2 + 1]
        large1 = a[n // 2 + 1:]
        small1.insert(0, small1[-1])
        del small1[-1]
        for i in range(n // 2):
            ans1.append(small1[i])
            ans1.append(large1[i])
        ans1.append(small1[n // 2])

        small2 = a[:n // 2]
        large2 = a[n // 2:]
        large2.append(large2[0])
        del large2[0]
        for i in range(n // 2):
            ans2.append(large2[i])
            ans2.append(small2[i])
        ans2.append(large2[n // 2])

        tmp_ans1 = 0
        tmp_ans2 = 0
        for i in range(1, n):
            tmp_ans1 += abs(ans1[i - 1] - ans1[i])
            tmp_ans2 += abs(ans2[i - 1] - ans2[i])

        print(max(tmp_ans1, tmp_ans2))

if __name__ == '__main__':
    main()

Solution (Python):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





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

    a.sort()

    ans1 = []
    ans2 = []
    if not n % 2:
        small = a[:n // 2]
        large = a[n // 2:]
        for i in range(n // 2):
            ans2.append(large[i])
            ans2.append(small[i])

        tmp_ans = 0
        for i in range(1, n):
            tmp_ans += abs(ans2[i - 1] - ans2[i])

        print(tmp_ans)

    else:
        small1 = a[:n // 2 + 1]
        large1 = a[n // 2 + 1:]
        small1.insert(0, small1[-1])
        del small1[-1]
        for i in range(n // 2):
            ans1.append(small1[i])
            ans1.append(large1[i])
        ans1.append(small1[n // 2])

        small2 = a[:n // 2]
        large2 = a[n // 2:]
        large2.append(large2[0])
        del large2[0]
        for i in range(n // 2):
            ans2.append(large2[i])
            ans2.append(small2[i])
        ans2.append(large2[n // 2])

        tmp_ans1 = 0
        tmp_ans2 = 0
        for i in range(1, n):
            tmp_ans1 += abs(ans1[i - 1] - ans1[i])
            tmp_ans2 += abs(ans2[i - 1] - ans2[i])

        print(max(tmp_ans1, tmp_ans2))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def tenka18beg_c():
    
    inp = list(map(int, read().split()))
    N = inp[0]
    A = inp[1:]
    A.sort()

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

tenka18beg_c()

Solution (Python):

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

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

tenka18beg_c()

Solution (Python):
def tenka18beg_c():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A_desc = sorted(A, reverse=True)

    if N % 2 == 1:
        tot1, tot2 = 0, 0
        for i, a in enumerate(A_desc):
            if i < N//2 - 1:
                tot1 += 2*a
                tot2 += 2*a
            elif i == N//2 - 1:
                tot1 += a
                tot2 += 2*a
            elif i == N//2:
                tot1 += a
                tot2 -= a
            elif i == N//2 + 1:
                tot1 -= 2*a
                tot2 -= a
            elif N//2 + 1 < i:
                tot1 -= 2*a
                tot2 -= 2*a
        ans = max(tot1, tot2)
    else:
        tot = 0
        for i, a in enumerate(A_desc):
            if i < N//2 - 1:
                tot += 2*a
            elif i == N//2 - 1:
                tot += a
            elif i == N//2:
                tot -= a
            elif N//2 < i:
                tot -= 2*a
        ans = tot
    print(ans)

tenka18beg_c()

Solution (Python):

from collections import deque
n = int(input())
nums = []
for _ in range(n):
    nums.append(int(input()))
nums.sort()
ans = 0
l = 0
r = n - 1
q = deque()
while l <= r:
    left = nums[l]
    right = nums[r]
    if not q:
        ans += abs(right - left)
        q.append(left)
        q.append(right)
        l += 1
        r -= 1
    else:
        s = max(abs(q[-1] - right), abs(q[0] - right))
        t = max(abs(q[-1] - left), abs(q[0] - left))
        if s >= t:
            if abs(q[-1] - right) > abs(q[0] - right):
                ans += abs(q[-1] - right)
                q.append(right)
            else:
                ans += abs(q[0] - right)
                q.appendleft(right)
            r -= 1
        else:
            if abs(q[-1] - left) > abs(q[0] - left):
                ans += abs(q[-1] - left)
                q.append(left)
            else:
                ans += abs(q[0] - left)
                q.appendleft(left)
            l += 1
print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for i 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]
elif n % 2 == 1:
    ans1 = sum(a[n//2+2:])*2 + a[n//2] + a[n//2+1] - sum(a[:n//2])*2
    ans2 = sum(a[n//2+1:])*2 -sum(a[:n//2-1])*2 -a[n//2] - a[n//2-1]
    ans = max(ans1,ans2)
print(ans)

Solution (Python):
N = int(input())
AA = [int(input()) for _ in range(N)]
AA.sort()
AF = AA[:N//2]
AL = AA[N//2:]
ans = 0
if N % 2 == 0:
    ans = sum(AL)*2 - AL[0] - sum(AF)*2 + AF[-1]
else:
    ans1 = sum(AL)*2 - sum(AF)*2 - sum(AL[0:2])
    ans2 = sum(AL)*2 - sum(AF)*2 - 3 * AL[0] + AF[-1]
    ans = max(ans1, ans2)


print(ans)

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

from collections import deque

def main():
    n = II()
    aa = [II() for _ in range(n)]
    aa.sort()
    maxv = 0
    if n%2==0:
        sumv = 0
        l = aa[:n//2]
        r = aa[n//2:]
        sumv += sum(2*ri for ri in r)
        sumv -= r[0]
        sumv -= sum(2*li for li in l)
        sumv += l[-1]
        maxv = max(maxv, sumv)
    else:
        sumv = 0
        l = aa[:n//2]
        r = aa[n//2:]
        sumv += sum(2*ri for ri in r)
        sumv -= r[0]+r[1]
        sumv -= sum(2*li for li in l)
        maxv = max(maxv, sumv)

        sumv = 0
        l = aa[:n//2+1]
        r = aa[n//2+1:]
        sumv += sum(2*ri for ri in r)
        sumv -= sum(2*li for li in l)
        sumv += l[-1]+l[-2]
        maxv = max(maxv, sumv)
    print(maxv)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    if N % 2 == 0:
        ans = A[N // 2] - A[N // 2 - 1]
        for i in range(N // 2 - 1):
            ans -= 2 * A[i]
        for i in range(N // 2 + 1, N):
            ans += 2 * A[i]
    else:
        ans1 = -A[N // 2] - A[N // 2 - 1]
        for i in range(N // 2 - 1):
            ans1 -= 2 * A[i]
        for i in range(N // 2 + 1, N):
            ans1 += 2 * A[i]

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

        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)])

    mid = n//2
    aa = sum(a[:mid])
    if n%2 == 0:
        ad = sum(a[mid:])
        print(2*(ad-aa)-(a[mid]-a[mid-1]))
        return 0
    ad = sum(a[mid+1:])
    tmp = min(a[mid+1]-a[mid],a[mid]-a[mid-1])
    print(2*(ad-aa)-tmp)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    A.sort()
    ans1=0
    if n%2==0:
        ans1=(2*sum(A[n//2:])-A[n//2])-(2*sum(A[:n//2])-A[n//2-1])
    else:
        ans1=(2*sum(A[n//2:])-A[n//2]-A[n//2+1])-2*sum(A[:n//2])
    ans2=0
    if n%2==0:
        ans2=(2*sum(A[n//2:])-A[n//2])-(2*sum(A[:n//2])-A[n//2-1])
    else:
        ans2=2*sum(A[n//2+1:])-(2*sum(A[:n//2+1])-A[n//2-1]-A[n//2])      
    print(max(ans1,ans2))

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    A.sort()
    ans1=0
    if n%2==0:
        ans1=(2*sum(A[n//2:])-A[n//2])-(2*sum(A[:n//2])-A[n//2-1])
    else:
        ans1=(2*sum(A[n//2:])-A[n//2]-A[n//2+1])-2*sum(A[:n//2])
    ans2=0
    if n%2==0:
        ans2=(2*sum(A[n//2:])-A[n//2])-(2*sum(A[:n//2])-A[n//2-1])
    else:
        ans2=2*sum(A[n//2+1:])-(2*sum(A[:n//2+1])-A[n//2-1]-A[n//2])      
    print(max(ans1,ans2))

if __name__=='__main__':
    main()