Problem:
 Score : 400 points    Problem Statement You are given N integers; the i -th of them is A_i .
Find the maximum possible sum of the absolute differences between the adjacent elements after arranging these integers in a row in any order you like.      Constraints  2 \leq N \leq 10^5  1 \leq A_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  :  A_N       Output Print the maximum possible sum of the absolute differences between the adjacent elements after arranging the given integers in a row in any order you like.        Sample Input 1 5
6
8
1
2
3      Sample Output 1 21  When the integers are arranged as 3,8,1,6,2 , the sum of the absolute differences between the adjacent elements is |3 - 8| + |8 - 1| + |1 - 6| + |6 - 2| = 21 . This is the maximum possible sum.       Sample Input 2 6
3
1
4
1
5
9      Sample Output 2 25       Sample Input 3 3
5
5
1      Sample Output 3 8

Solution (Python):
def calc_score(li):
    prev = li[0]
    ret = 0
    for el in li:
        ret += abs(el - prev)
        prev = el
    return ret


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

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

from collections import deque
que = deque(A)


ans = deque([que.popleft()])
cur = 0
while que:
    if cur % 2 == 0:
        ans.appendleft(que.pop())
        if len(que):
            ans.append(que.pop())
        cur ^= 1
    else:
        ans.appendleft(que.popleft())
        if len(que):
            ans.append(que.popleft())
        cur ^= 1

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


que = deque(A)
ans = deque([que.pop()])
cur = 1
while que:
    if cur % 2 == 0:
        ans.appendleft(que.pop())
        if len(que):
            ans.append(que.pop())
        cur ^= 1
    else:
        ans.appendleft(que.popleft())
        if len(que):
            ans.append(que.popleft())
        cur ^= 1

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

print(max(res1, res2))

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

    ans1 = 0
    ans2 = 0
    if N & 1:
        
        a1 = sum(A[N//2+2:])*2+A[N//2+1]+A[N//2]-sum(A[:N//2])*2
        
        a2 = sum(A[N//2+1:])*2-A[N//2]-A[N//2-1]-sum(A[:N//2-1])*2
        print(max(a1,a2))
    else:
        print(sum(A[N//2+1:])*2-sum(A[:N//2-1])*2-A[N//2-1]+A[N//2])










main()

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, *A = map(int, open(0))
    A.sort()
    ans = 0
    if N % 2 == 1:
        ans += sum(A[N//2:])*2 - sum(A[:N//2])*2
        ans -= A[N//2]+A[N//2+1]
    else:
        ans += sum(A[N//2:])*2 - sum(A[:N//2])*2
        ans -= A[N//2]-A[N//2-1]
    

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

    print(max(ans,ans2))

if __name__ == "__main__":
    main()

Solution (Python):
n, *A = map(int, open(0).read().split())
a=sorted(A)
if n%2:
    print(sum(a[-n//2+1:])*2 - sum(a[:n//2])*2 - min(a[n//2+1]-a[n//2],a[n//2]-a[n//2-1]))
else:
    print(sum(a[n//2+1:])*2 -sum(a[:n//2-1])*2 +a[n//2] -a[n//2-1])

Solution (Python):
n, *A = map(int, open(0).read().split())
a=sorted(A)
if n%2:
    print(sum(a[-n//2+1:])*2 - sum(a[:n//2])*2 - min(a[n//2+1]-a[n//2],a[n//2]-a[n//2-1]))
else:
    print(sum(a[n//2+1:])*2 -sum(a[:n//2-1])*2 +a[n//2] -a[n//2-1])

Solution (Python):

n, *A = map(int, open(0).read().split())
a=sorted(A)
if n%2:
    print(sum(a[-n//2+1:])*2 - sum(a[:n//2])*2 - min(a[n//2+1]-a[n//2],a[n//2]-a[n//2-1]))
else:
    print(sum(a[n//2+1:])*2 -sum(a[:n//2-1])*2 +a[n//2] -a[n//2-1])

Solution (Python):
import sys
from collections import deque
import copy

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def calc(N, A, max_min):

    if max_min:
        al = deque([A.popleft()])
        f = True
    else:
        al = deque([A.pop()])
        f = False

    while A:
        if len(A) >= 2:
            if f:
                al.append(A.pop())
                al.appendleft(A.pop())
                f = False
            else:
                al.appendleft(A.popleft())
                al.append(A.popleft())
                f = True

        elif len(A) == 1:
            al.append(A.pop())

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

    return ans


def main():
    N = in_n()
    A = deque(sorted(list(in_na())))

    ans1 = calc(N, copy.copy(A), True)
    ans2 = calc(N, copy.copy(A), False)
    print(max(ans1, ans2))


if __name__ == '__main__':
    main()

Solution (Python):

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [None]*n
for i in range(n):
    a[i] = int(input())
    
a.sort()
b = [None]*n
if n%2==0:
    b[0] = a[n//2-1]
    b[-1] = a[n//2]
    l1 = a[:n//2-1]
    l2 = a[n//2+1:][::-1]
    for i in range(len(l1)):
        b[2*i+1] = l2[i]
        b[2*i+2] = l1[i]
    ans = sum(abs(b[i]-b[i+1]) for i in range(n-1))
else:
    ind = n//2+1
    b[0] = a[ind]
    b[-1] = a[n//2]
    l1 = a[:n//2]
    l2 = a[ind:][::-1]
    b[1] = l1[0]
    for i in range(len(l1)-1):
        b[2*i+2] = l2[i]
        b[2*i+3] = l1[i+1]
    ans1 = sum(abs(b[i]-b[i+1]) for i in range(n-1))
    
    ind = n//2-1
    b[0] = a[n//2]
    b[-1] = a[ind]
    l1 = a[:ind]
    l2 = a[n//2+1:]
    b[1] = l2[0]
    for i in range(len(l2)-1):
        b[2*i+2] = l1[i]
        b[2*i+3] = l2[i+1]
    ans2 = sum(abs(b[i]-b[i+1]) for i in range(n-1))
    ans = max(ans1, ans2)
print(ans)

Solution (Python):
n = int(input())
a = sorted(list(int(input()) for _ in range(n)))

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

Solution (Python):
n=int(input())
ans=[]
for i in range(n):
  ans.append(int(input()))
ans.sort()
counter=0
re=[]
for i in range(n):
  re.append(ans[i])
re.reverse()
pointer1=0
pointer2=0
thing=0
a=[]
while counter<n-2:
  if thing==0:
    a.append(ans[pointer1])
    pointer1+=1
    thing=1
  else:
    a.append(re[pointer2])
    pointer2+=1
    thing=0
  counter+=1
final=[]
final.append(re[pointer2])
for i in a:
  final.append(i)
final.append(ans[pointer1])
maxans=0
for i in range(n-1):
  maxans+=abs(final[i]-final[i+1])
pointer1=0
pointer2=0
thing=1
a=[]
counter=0
while counter<n-2:
  if thing==0:
    a.append(ans[pointer1])
    pointer1+=1
    thing=1
  else:
    a.append(re[pointer2])
    pointer2+=1
    thing=0
  counter+=1
final=[]
final.append(re[pointer2])
for i in a:
  final.append(i)
final.append(ans[pointer1])
maxans1=0
for i in range(n-1):
  maxans1+=abs(final[i]-final[i+1])
print(max(maxans1,maxans))

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

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

Solution (Python):
from collections import deque
from copy import deepcopy

n,*a = map(int,open(0).read().split())
acopy = deepcopy(a)
a.sort()
acopy.sort(reverse = True)

L = deque([])
a = deque(a)
acopy = deque(acopy)
Lcopy = deepcopy(L)

max_ = a.pop()
L.append(max_)
min_ = acopy.pop()
Lcopy.append(min_)

while a:
    if a:
        b = a.popleft()
        L.append(b)
    if a:
        c = a.popleft()
        L.appendleft(c)
    if a:
        d = a.pop()
        L.append(d)
    if a:
        e = a.pop()
        L.appendleft(e)

while acopy:
    if acopy:
        b = acopy.popleft()
        Lcopy.append(b)
    if acopy:
        c = acopy.popleft()
        Lcopy.appendleft(c)
    if acopy:
        d = acopy.pop()
        Lcopy.append(d)
    if acopy:
        e = acopy.pop()
        Lcopy.appendleft(e)
ans1,ans2 = 0,0

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

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



if n & 1 == 0:
    x1 = n // 2
    x2 = x1 - 1
    res = 0
    for i in range(n):
        if i < x2:
            res += (dat[i]) * -2
            continue
        if i == x2:
            res += (dat[i]) * -1
            continue
        if i == x1:
            res += (dat[i])
            continue
        if i > x1:
            res += (dat[i]) * 2
            continue
    print(res)
else:
    xc = n // 2
    xl = xc - 1
    xr = xc + 1

    res = 0
    for i in range(n):
        if i < xl:
            res += (dat[i]) * -2
            continue
        if i == xl:
            res += (dat[i]) * -1
            continue
        if i == xc:
            res += (dat[i]) * -1
            continue
        if i > xc:
            res += (dat[i]) * 2
            continue

    res2 = 0
    for i in range(n):
        if i < xc:
            res2 += (dat[i]) * -2
            continue
        if i == xc:
            res2 += (dat[i]) * 1
            continue
        if i == xr:
            res2 += (dat[i]) * 1
            continue
        if i > xr:
            res2 += (dat[i]) * 2
            continue

    print(max(res, res2))

Solution (Python):
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
a = sorted(a)
from collections import deque
q = deque([])
q.extend(a)
p = deque([])
i = 0
while len(q) > 1:
    if i%2 == 0:
        p.appendleft(q.popleft())
        p.append(q.pop())
    else:
        p.append(q.popleft())
        p.appendleft(q.pop())
    i += 1
p1 = list(p) + list(q)
p2 = list(q) + list(p)
ans1 = 0
ans2 = 0
for i in range(n-1):
    ans1 += abs(p1[i+1]-p1[i])
    ans2 += abs(p2[i+1]-p2[i])
print(max(ans1,ans2))

Solution (Python):
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
a = sorted(a)
from collections import deque
q = deque([])
q.extend(a)
p = deque([])
i = 0
while len(q) > 1:
    if i%2 == 0:
        y = q.popleft()
        p.appendleft(y)
        
        x = q.pop()
        p.append(x)
            
    else:
        y = q.popleft()
        p.append(y)
        
        x = q.pop()
        p.appendleft(x)
    i += 1
p1 = list(p) + list(q)
p2 = list(q) + list(p)
ans1 = 0
ans2 = 0
for i in range(n-1):
    ans1 += abs(p1[i+1]-p1[i])
    ans2 += abs(p2[i+1]-p2[i])
print(max(ans1,ans2))

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

N = i()
A = []
for j in range(N):
    a = i()
    A.append(a)

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

print(ans)

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union








from collections import deque                





















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def calc_max_diff(seq):
        n = len(seq)
        total = 0
        min_diff = inf
        for i in range(1, n):
            diff = abs(seq[i] - seq[i-1])
            total += diff
            min_diff = min(min_diff, diff)
        diff = abs(seq[0] - seq[-1])
        total += diff
        min_diff = min(min_diff, diff)
        return total - min_diff

    
    n = ii()
    L = [ii() for _ in range(n)]
    
    L.sort()
    dq = deque(L)
    large_small = []
    while dq:
        
        large_small.append(dq.pop())
        if dq:
            large_small.append(dq.popleft())

    dq = deque(L)
    small_large = []
    while dq:
        small_large.append(dq.popleft())
        if dq:
            small_large.append(dq.pop())


    a = calc_max_diff(large_small)
    b = calc_max_diff(small_large)
    
    print(max(a, b))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,gcd
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')



 
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n=ii()
arr=deque(list(sorted([ii() for _ in range(n)])))
cop=deque(deepcopy(list(arr)))
mat=deque([])

for i in range(n):
    if i%4==0:
        p=arr.popleft()
        mat.append(p)
    elif i%4==1:
        p=arr.pop()
        mat.appendleft(p)
    elif i%4==2:
        p=arr.pop()
        mat.append(p)
    else:
        p=arr.popleft()
        mat.appendleft(p)

mat2=deque([])
for i in range(n):
    if i%4==0:
        p=cop.pop()
        mat2.append(p)
    elif i%4==1:
        p=cop.popleft()
        mat2.appendleft(p)
    elif i%4==2:
        p=cop.popleft()
        mat2.append(p)
    else:
        p=cop.pop()
        mat2.appendleft(p)

ans=0
ans1=0
chk=list(mat)
chk1=list(mat2)
for i in range(n-1):
    ans+=abs(chk[i]-chk[i+1])
    ans1+=abs(chk1[i]-chk1[i+1])
print(max(ans,ans1))

Solution (Python):
from collections import deque

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    D = deque(A)
    d = D.popleft()
    tmp = deque([d])
    cnt = 0
    while D:
        if cnt % 2 == 0:
            i = D.pop()
            tmp.appendleft(i)
            if D:
                j = D.pop()
                tmp.append(j)
        else:
            i = D.popleft()
            tmp.appendleft(i)
            if D:
                j = D.popleft()
                tmp.append(j)
        cnt += 1

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

    D = deque(A)
    d = D.pop()
    tmp = deque([d])
    cnt = 0
    while D:
        if cnt % 2 == 0:
            i = D.popleft()
            tmp.appendleft(i)
            if D:
                j = D.popleft()
                tmp.append(j)

        else:
            i = D.pop()
            tmp.appendleft(i)
            if D:
                j = D.pop()
                tmp.append(j)
        cnt += 1

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

    print(max(a,ans))

if __name__ == "__main__":
    main()

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

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

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

a.sort()

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

Solution (Python):
n=int(input())
a=sorted([int(input()) for _ in range(n)])
f=0
ans=0
while a:
  f^=1
  if len(a)==3 and n%2==1:
    ans+=max(3*max(a)-sum(a),sum(a)-3*min(a))
    break
  ans+=([-1,1][f])*(2 if len(a)>2 else 1)*a.pop(-f)
print(ans)

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

A.sort()
B=[]
C=[]
if N%2==1:
    m=A[N//2]
    ans=0
    for i in range(N//2):
        B.append(A[i])
        C.append(A[-1-i])
        B.append(A[-1-i])
        C.append(A[i])
    dB=abs(m-B[0])
    dC=abs(m-C[0])
    for j in range(1,len(B)):
        dB+=abs(B[j]-B[j-1])
        dC+=abs(C[j]-C[j-1])
    ans=max(dB,dC)
else:
    for i in range(N//2):
        B.append(A[i])
        C.append(A[-1-i])
        B.append(A[-1-i])
        C.append(A[i])
    dB=abs(B[-1]-B[0])
    dC=abs(C[-1]-C[0])
    for j in range(1,len(B)-1):
        dB+=abs(B[j]-B[j-1])
        dC+=abs(C[j]-C[j-1])
    ans=max(dB,dC)
print(ans)

Solution (Python):
n = int(input())
if n == 1:
    print(0)
    exit()
a = [int(input()) for _ in range(n)]
a.sort()
na = [0]*n
c = n//2
if n%2 == 1:
    if a[c]-a[c-1] < a[c+1]-a[c]:
        lst1 = a[:c+1]
        lst2 = a[c+1:]
    else:
        lst1 = a[c:][::-1]
        lst2 = a[:c]
    na[0] = lst1[-1]
    na[-1] = lst1[-2]
else:
    lst1 = a[:c]
    lst2 = a[c:][::-1]
    na[0] = lst1[-1]
    na[-1] = lst2[-1]
i1 = i2 = 0
for i in range(1,n-1):
    if i%2 == 0:
        na[i] = lst1[i1]
        i1 += 1
    else:
        na[i] = lst2[i2]
        i2 += 1

ans = 0
for i in range(1,n): ans += abs(na[i]-na[i-1])
print(ans)

Solution (Python):
n = int(input())
if n ==1:
    print(0)
    exit()
a = [int(input()) for _ in range(n)]
a.sort()
na = [0]*n
c = n//2
if n%2 == 1:
    if a[c]-a[c-1] < a[c+1]-a[c]:
        lst1 = a[:c+1]
        lst2 = a[c+1:]
        na[0] = lst1[-1]
        na[-1] = lst1[-2]
    else:
        lst1 = a[c:][::-1]
        lst2 = a[:c]
        na[0] = lst1[-1]
        na[-1] = lst1[-2]
else:
    lst1 = a[:c]
    lst2 = a[c:][::-1]
    na[0] = lst1[-1]
    na[-1] = lst2[-1]
i1 = i2 = 0
for i in range(1,n-1):
    if i%2 == 0:
        na[i] = lst1[i1]
        i1 += 1
    else:
        na[i] = lst2[i2]
        i2 += 1

ans = 0
for i in range(1,n): ans += abs(na[i]-na[i-1])
print(ans)

Solution (Python):



from collections import deque

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

    lnow = A.pop()
    rnow = lnow
    ret = 0
    while len(A)>0:
        lnxt = A[0]
        rnxt = A[-1]
        ll = abs(lnow - lnxt)
        rl = abs(rnow - lnxt)
        lr = abs(lnow - rnxt)
        rr = abs(rnow - rnxt)
        mx = max(ll, rl, lr, rr)
        ret += mx
        if mx == ll:
            lnow = lnxt
            x = A.popleft()
        elif  mx == rl:
            rnow = lnxt
            x = A.popleft()
        elif  mx == lr:
            lnow = rnxt
            x = A.pop()
        elif  mx == rr:
            rnow = rnxt
            x = A.pop()

    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


N = INT()
A = [INT() for _ in range(N)]

A.sort()

if N%2 == 0:
	a = A[:N//2]
	b = A[N//2:]

	print((2*sum(b)-b[0]) - (2*sum(a)-a[-1]))

else:
	a1 = A[:N//2]
	b1 = A[N//2:]

	ans1 = (2*sum(b1)-b1[0]-b1[1]) - 2*sum(a1)

	a2 = A[:-(-N//2)]
	b2 = A[-(-N//2):]

	ans2 = (2*sum(b2)) - (2*sum(a2)-a2[-1]-a2[-2])

	print(max(ans1, ans2))

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

p = [0]*n
m = [0]*n

for i in range(n-1):
    if i%2:
        m[i] += 1
        p[i+1] += 1
    else:
        p[i] += 1
        m[i+1] += 1
p.sort(reverse=True)
m.sort(reverse=True)
ans = 0
for i in range(n):
    if m[i] <= 0:
        break
    ans -= m[i]*a[i]
for i in range(n):
    if p[i] <= 0:
        break
    ans += p[i]*a[-1-i]
ans2 = 0
for i in range(n):
    if p[i] <= 0:
        break
    ans2 -= p[i]*a[i]
for i in range(n):
    if m[i] <= 0:
        break
    ans2 += m[i]*a[-1-i]

print(max(ans,ans2))

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
As = sorted([int(input()) for i in range(n)])
q = deque(As[1:])

ans = 0
cnt = 1
p1 = As[0]
p2 = As[0]
flg = False
while True:
    if len(q) == 0: break
    if flg:
        n1 = q.popleft()
    else:
        n1 = q.pop()
    ans += abs(p1-n1)
    p1 = n1

    if len(q) == 0: break
    if flg:
        n2 = q.popleft()
    else:
        n2 = q.pop()
    ans += abs(p2-n2)
    p2 = n2

    flg = not flg


As = As[::-1]
ans2 = 0
p1 = As[0]
p2 = As[0]
q = deque(As[1:])
flg = False
while True:
    if len(q) == 0: break
    if flg:
        n1 = q.popleft()
    else:
        n1 = q.pop()
    ans2 += abs(p1-n1)
    p1 = n1

    if len(q) == 0: break
    if flg:
        n2 = q.popleft()
    else:
        n2 = q.pop()
    ans2 += abs(p2-n2)
    p2 = n2

    flg = not flg


print(max(ans,ans2))

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
A = ILs(N)
A.sort()

if N == 3:
  a,b,c = A
  print(max(abs(a-c)+abs(a-b),abs(a-c)+abs(c-b)))
  exit()

if N%2:
  U1 = A[-(-N//2):]
  D1 = A[:-(-N//2)]
  ans1= (sum(U1)-sum(D1))*2+D1[-1]+D1[-2]
  
  U2 = A[N//2:]
  D2 = A[:N//2]
  ans2= (sum(U2)-sum(D2))*2-U2[0]-U2[1]
  
  print(max(ans1,ans2))
else:
  U = A[N//2:]
  D = A[:N//2]
  print((sum(U)-sum(D))*2-U[0]+D[-1])

Solution (Python):
from collections import deque
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
a.sort()
d = deque(a)
ans = deque([d.popleft()])
cur = 0
while d:
    if cur%2 == 0:
        ans.appendleft(d.pop())
        if len(d) != 0:
            ans.append(d.pop())
        cur += 1
    else:
        ans.appendleft(d.popleft())
        if len(d) != 0:
            ans.append(d.popleft())
        cur += 1
p = 0
for x, y in zip(list(ans), list(ans)[1:]):
    p += abs(x-y)

d = deque(a)
ans = deque([d.pop()])
cur = 1
while d:
    if cur%2 == 0:
        ans.appendleft(d.pop())
        if len(d) != 0:
            ans.append(d.pop())
        cur += 1
    else:
        ans.appendleft(d.popleft())
        if len(d) != 0:
            ans.append(d.popleft())
        cur += 1
q = 0
for x, y in zip(list(ans), list(ans)[1:]):
    q += abs(x-y)
print(max(p, q))

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n = ir()
a = [ir() for i in range(n)]
a.sort()
ans = [0,0]

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

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

    for i in range(n//2):
        ans[1]-=2*a[i]
    ans[1]-=a[n//2]
    ans[1]+=a[n//2+1]
    for i in range(n//2+2,n):
        ans[1]+=2*a[i]
else:
    for i in range(n//2):
        ans[0]-=2*a[i]
    ans[0]+=a[n//2]
    ans[0]+=a[n//2+1]
    for i in range(n//2+2,n):
        ans[0]+=2*a[i]

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

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

m = n//2
a1 = a[:m]
a2 = a[:m-1:-1]
if n%2==1:a1.append(a[m])

from collections import deque
l = deque([])

for i in range(m):
    if i%2==0:
        l.append(a1[i])
        l.appendleft(a2[i])
    else:
        l.append(a2[i])
        l.appendleft(a1[i])

if n%2==1:
    if abs(l[0]-a1[-1])>abs(l[-1]-a1[-1]):
        l.appendleft(a1[-1])
    else:
        l.append(a1[-1])

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

print(ans)