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

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

if n % 2 == 0:
    for i in range(n//2):
        b.append(a[i])
        b.append(a[-(i+1)])
else:
    for i in range(n//2):
        b.append(a[i])
        b.append(a[-(i+1)])
    b.append(a[n//2])

ans = 0
for i in range(n-1):
    ans += abs(b[i] - b[i+1])
ans += abs(b[0] - b[n-1])
b.sort()
if n % 2 == 0:
    ans -= abs(b[n // 2] - b[n // 2 - 1])
else:
    ans -= min(abs(b[n//2] - b[n//2-1]), abs(b[n//2] - b[n//2+1]))

print(ans)

Solution (Python):





"""
Tenka1-2018 C
"""

n = int(input())
ali = [int(input()) for i in range(n)]
ali.sort()

if n % 2 is 1:
    m = (n-1)//2
    am = ali[m]
    asmall = ali[:m]
    abig = ali[m+1:]
    if 2*am-asmall[-1]-abig[0] > 0:
        ans = am-2*sum(asmall)+2*sum(abig)-abig[0]
    else:
        ans = -am+2*sum(abig)-2*sum(asmall)+asmall[-1]
else:
    m = n//2
    asmall = ali[:m]
    abig = ali[m:]
    ans = -2*sum(asmall)+2*sum(abig)-abig[0]+asmall[-1]

print(ans)

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

c = v[n // 2]
ans = 0
for i in range(n):
    ans += 2 * abs(v[i] - c)

if (n % 2 == 0):
    ans -= c - v[n//2 - 1]
else:
    ans -= min(v[n//2+1]-c, c-v[n//2-1])

print(ans)

Solution (Python):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


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


A.sort()

dp1 = [0]*N
dp2 = [0]*N

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

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


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

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

Solution (Python):

N = int(input())
A = sorted([int(input()) for _ in range(N)])
ans = 0
if N%2 == 0:
    B = []
    for i in range(N//2)[::-1]:
        if i%2:
            B.append(-i-1)
        else:
            B.append(i)
    for i in range(N//2):
        if i%2:
            B.append(i)
        else:
            B.append(-i-1)
    S = [A[b] for b in B]
    for i in range(N-1):
        ans += abs(S[i+1] - S[i])
else:
    M = N//2
    B = list(range(1, M+2))[::-1] + list(range(1, M+1))
    S = []
    for i, b in enumerate(B):
        if i%2:
            S.append(A[-b])
        else:
            S.append(A[b-1])
    for i in range(N-1):
        ans += abs(S[i+1] - S[i])

    S = []
    for i, b in enumerate(B):
        if i%2:
            S.append(A[b-1])
        else:
            S.append(A[-b])
    tmp = 0
    for i in range(N-1):
        tmp += abs(S[i+1] - S[i])
    ans = max(ans, tmp)
print(ans)

Solution (Python):


import math
import sys
import itertools
import numpy as np



n =int(input())


a = [int(input()) for i in range(n)] 
a = sorted(a)
b=[0]*(n//2)
c=[0]*(n//2)
answer = 0
for i in range(0,n//2):
    b[i] = a[i]
    c[i] = a[n-i-1]
answer += c[0] - b[0]
for i in range(1,n//2):
    answer += c[i-1] - b[i]
    answer += c[i] - b[i-1]


if n % 2 == 1:
    answer += max(c[-1]-a[(n-1)//2],a[(n-1)//2]-b[-1])

print(answer)

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

a.sort()

left = 0
right = n - 1
mid = right // 2
ans1 = abs(a[mid] - a[right])
while(True):
    if(left == mid or right == mid): break
    ans1 += abs(a[right] - a[left])
    right -= 1

    if(left == mid or right == mid): break
    ans1 += abs(a[right] - a[left])
    left += 1
    

left = 0
right = n - 1
mid = right // 2
if(right % 2 != 0): mid += 1
ans2 = abs(a[mid] - a[left])
while(True):
    if(left == mid or right == mid): break
    ans2 += abs(a[right] - a[left])
    left += 1

    if(left == mid or right == mid): break
    ans2 += abs(a[right] - a[left])
    right -= 1

if(ans1 > ans2): print(ans1)
else: print(ans2)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

n = ni()
a = []
for _ in range(n):
    a.append(ni())
    
mx_cent = [ai for ai in a]
mn_cent = [ai for ai in a]    

a.sort()
a = deque(a)

mx_cent = deque([ai for ai in a])
mn_cent = deque([ai for ai in a])


bmx = deque([mx_cent.pop()])
bmn = deque([mn_cent.popleft()])

cnt = 0


while len(mx_cent) > 1:
    lf = 0
    rt = 0
    if cnt % 2 == 0:
        lf = mx_cent.popleft()
        rt = mx_cent.popleft()
    else:
        lf = mx_cent.pop()
        rt = mx_cent.pop()
    
    bmx.appendleft(lf)
    bmx.append(rt)
    
    
    if cnt % 2 == 0:
        lf = mn_cent.pop()
        rt = mn_cent.pop()
    else:
        lf = mn_cent.popleft()
        rt = mn_cent.popleft()
    
    bmn.appendleft(lf)
    bmn.append(rt)
    
    cnt += 1


if len(mx_cent) == 1:
    last = mx_cent.pop()
    if abs(bmx[0] - last) > abs(bmx[-1] - last):
        bmx.appendleft(last)
    else:
        bmx.append(last)
        
    last = mn_cent.pop()
    if abs(bmn[0] - last) > abs(bmn[-1] - last):
        bmn.appendleft(last)
    else:
        bmn.append(last)

diffmx, diffmn = 0, 0        
for i in range(n-1):
    diffmx += abs(bmx[i+1] - bmx[i])
    diffmn += abs(bmn[i+1] - bmn[i])
    
print(max(diffmx, diffmn))

Solution (Python):
 
import collections, atexit, math, sys, bisect 
 
def getIntList():
    return list(map(int, input().split()))    
 
 
N, = getIntList()

za = []
for i in range(N):
    a = input()
    a = int(a)
    za.append(a)

za.sort()

if N%2==0:
    t = N//2
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res = s1*2 - s0 *2  - za[t] + za[t-1]
else:
    t = N//2 + 1
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res0 = s1 *2 - s0*2 + za[t-1] + za[t-2]
    t = t - 1
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res1 = s1 *2 - s0*2 -  za[t] - za[t+1]
    res = max(res1, res0)

print(res)

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

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

A.sort()

if N % 2 == 0:
    start = N // 2 - 1
    end = start + 1
else:
    start = N // 2
    if A[start] - A[start-1] > A[start+1] - A[start]:
        end = start + 1
    else:
        end = start - 1

result = 0

for i in range(N):
    if i == start or i == end:
        result += abs(A[i] - A[start])
    else:
        result += abs(A[i] - A[start]) * 2

print(result)

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

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2-1], A[N//2]
    del A[N // 2-1]
    del A[N // 2-1]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)

Solution (Python):

from collections import deque

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

	v1 = nums.popleft()
	v2 = nums.pop()
	ans = v2 - v1
	
	
	while len(nums) > 0:
		w1 = abs(nums[-1] - v1)
		w2 = abs(nums[-1] - v2)
		w3 = abs(nums[0] - v1)
		w4 = abs(nums[0] - v2)
		max_w = max(w1, w2, w3, w4)
		
		if w1 == max_w:
			ans += w1
			v1 = nums.pop()
		elif w2 == max_w:
			ans += w2
			v2 = nums.pop()
		elif w3 == max_w:
			ans += w3
			v1 = nums.popleft()
		else:
			ans += w4
			v2 = nums.popleft()
		
	print(ans)

	


if __name__ == '__main__':
	main()

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

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

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

Solution (Python):
from sys import stdin
def main():
    n = int(stdin.readline())
    a = [int(stdin.readline()) for _ in xrange(n)]
    a.sort()
    h = n / 2
    def solve(l, m):
        res = sum(m) - sum(l)
        res *= 2
        if len(l) < len(m):
            res -= m[0] + m[1]
        else:
            res += l[-1] + l[-2]
        return res
    if n % 2:
        print max(solve(a[:h], a[h:]), solve(a[:h+1], a[h+1:]))
    else:
        ans = 0
        for i in xrange(n / 2):
            ans += a[i+h] - a[i]
        ans = ans * 2 + a[h-1] - a[h]
        print ans
main()

Solution (Python):
from collections import deque
n = int(input())
a = deque([])
for i in range(n):
  x = int(input())
  a.append(x)
a=sorted(a)
a1 = deque(a)
b = deque([])
b.append(a1.popleft())
i = 0
while a1:
  if i%2 == 1:
    b.append(a1.popleft())
    if a1 == deque([]):
      break
    b.appendleft(a1.popleft())
    i += 1
  else:
    b.append(a1.pop())
    if a1 == deque([]):
      break
    b.appendleft(a1.pop())
    i += 1
ans = 0
for i in range(1,n):
  ans += abs(b[i] - b[i-1])
a = deque(a)
b = deque([])
b.append(a.pop())
i = 0
while a:
  if i%2 == 0:
    b.append(a.popleft())
    if a == deque([]):
      break
    b.appendleft(a.popleft())
    i += 1
  else:
    b.append(a.pop())
    if a == deque([]):
      break
    b.appendleft(a.pop())
    i += 1
ans2 = 0
for i in range(1,n):
  ans2 += abs(b[i] - b[i-1])
ans = max(ans,ans2)
print(ans)

Solution (Python):

N = int(input())
A_list = [0]*N
for i in range(N):
    A_list[i] = int(input())
res = 0
A_list_s = sorted(A_list)

if N % 2 == 0:
    bar = A_list_s[N // 2]
    for i in range(N // 2):
        res += 2*(bar - A_list_s[i]) + 2*(A_list_s[N-1-i] - bar)
    res -= bar - A_list_s[N // 2 - 1]
else:
    bar = A_list_s[N // 2]
    for i in range(N // 2):
        res += 2*(bar - A_list_s[i]) + 2*(A_list_s[N-1-i] - bar)
    res -= min(bar - A_list_s[N // 2 - 1], A_list_s[N // 2 + 1] - bar)
print(res)

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
def calc(A):
    p = 0; q = N-2
    l = r = A[N-1]
    res = 0
    while p < q:
        a = A[p]; b = A[p+1]
        res += abs((l+r) - (a+b))
        p += 2
        l = a; r = b

        if not p < q:
            break

        a = A[q]; b = A[q-1]
        res += abs((l+r) - (a+b))
        l = a; r = b
        q -= 2

    if p == q:
        v = A[p]
        res += max(abs(l-v), abs(r-v))
    return res
s = calc(A)
A.reverse()
t = calc(A)

print(max(s, t))

Solution (Python):
import sys

n = int(input())
aaa = [int(line) for line in sys.stdin.readlines()]
aaa.sort()
if n % 2 == 0:
    m1, m2 = aaa[n // 2 - 1], aaa[n // 2]
    mid = sum(abs(a - m1) for a in aaa)
    ans = mid * 2 - (m2 - m1)
else:
    m1, m2, m3 = aaa[n // 2 - 1], aaa[n // 2], aaa[n // 2 + 1]
    mid = sum(abs(a - m2) for a in aaa)
    ans = mid * 2 - min(m2 - m1, m3 - m2)
print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
a = sorted(a)
res = a[-1]-a[0]
minn,maxx = a[0],a[-1]
for i in range(1,n//2):
    res += maxx - a[i]
    res += a[-1-i] - minn
    minn,maxx = a[i],a[-1-i]
if n%2==1:
    res += max(abs(maxx-a[n//2]),abs(minn-a[n//2]))
print(res)