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



Sample input:
5
6
8
1
2
3


Sample output:
21

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline

def calc_sum(replaced_list):
    max_sum = 0
    for i in range(len(replaced_list) - 1):
        left, right = replaced_list[i], replaced_list[i + 1]
        max_sum += abs(left - right) 
    return max_sum


def calc_replaced_even(N, A_list, left_mid, right_mid):
    replaced_list = [None] * N
    replaced_list[0] = A_list[left_mid]
    replaced_list[-1] = A_list[right_mid]
    for i in range(1, N//2):
        replaced_list[2 * i - 1] = A_list[-i]
        replaced_list[2 * i] = A_list[i - 1]
    return replaced_list


def calc_replaced_odd(N, A_list, left_mid, right_mid):
    replaced_list = [None] * N
    replaced_list[0] = A_list[left_mid]
    replaced_list[-1] = A_list[right_mid]
    if left_mid == N // 2 - 1:
        replaced_list[1] = A_list[-1]
        for i in range(1, left_mid + 1):
            replaced_list[2 * i] = A_list[i - 1]
            replaced_list[2 * i + 1] = A_list[-(i + 1)]
    else:
        replaced_list[-2] = A_list[0]
        for i in range(1, left_mid):
            replaced_list[2 * i - 1] = A_list[i]
            replaced_list[2 * i] = A_list[-i]
    return replaced_list


def calc_max_sum(replaced_list):
    max_sum = calc_sum(replaced_list)
    replaced_list[1:N-1] = replaced_list[1:N-1][::-1]
    return max(max_sum, calc_sum(replaced_list))


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

A_list.sort()
replaced_list = [None] * N
if N % 2 == 0:
    left_mid = N // 2 - 1
    right_mid = N // 2
    replaced_list = calc_replaced_even(N, A_list, left_mid, right_mid)
    max_sum = calc_max_sum(replaced_list)
    print(max_sum)
else:
    # try 2 types
    max_sum = 0
    for left_mid, right_mid in ((N // 2 - 1, N // 2), (N // 2, N // 2 + 1)):
        replaced_list = calc_replaced_odd(N, A_list, left_mid, right_mid)
        max_sum = max(max_sum, calc_max_sum(replaced_list))
    print(max_sum)

Submission status: Accepted

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

arr = []
for i in range(N//2):
    arr.append(A[i])
    arr.append(A[-1-i])
if N%2:
    arr.append(A[N//2])

tmp = 0
for a,b in zip(arr,arr[1:]):
    tmp += abs(a-b)

ans = tmp
for i in range(N):
    arr.append(arr[i])
    gain = abs(arr[-1] - arr[-2]) - abs(arr[i] - arr[i+1])
    tmp += gain
    ans = max(tmp, ans)



arr = []
for i in range(N//2):
    arr.append(A[-1-i])
    arr.append(A[i])
if N%2:
    arr.append(A[N//2])

tmp = 0
for a,b in zip(arr,arr[1:]):
    tmp += abs(a-b)

for i in range(N):
    arr.append(arr[i])
    gain = abs(arr[-1] - arr[-2]) - abs(arr[i] - arr[i+1])
    tmp += gain
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
 
A.sort()
As_ = A[:N//2]
Ab_ = A[N//2:]
A.reverse()
Ab = A[:N//2]
As = A[N//2:]
if N%2 == 0:
    if N == 2:
        ans = abs(A[0] - A[1])
    else:
        ans = sum(Ab[:-1])*2 + Ab[-1] - As[0] - sum(As[1:])*2
else:
    if N == 3:
        ans = max([A[0]*2-A[1]-A[2], A[0]+A[1]-A[2]*2])
    else:
        ans1 = sum(Ab)*2 - sum(As[2:])*2 - As[0] - As[1]
        ans2 = sum(Ab_[2:])*2 + Ab_[0] + Ab_[1] - sum(As_)*2
        ans = max([ans1, ans2])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

A.sort()

right = A[0]
left = A[0]
index_l = 1
index_r = len(A)-1
ans_l = 0
count = 1
while(1):
	if count % 2 == 1:
		if index_r - index_l >= 1:
			if abs(left-A[index_r])+abs(right-A[index_r-1]) > abs(right-A[index_r])+abs(left-A[index_r-1]):
				ans_l += abs(left-A[index_r])+abs(right-A[index_r-1])
				left = A[index_r]
				right = A[index_r-1]
			else:
				ans_l += abs(right-A[index_r])+abs(left-A[index_r-1])
				left = A[index_r-1]
				right = A[index_r]
			index_r -= 2
		elif index_r - index_l == 0:
			if abs(left-A[index_r]) > abs(right-A[index_r]):
				ans_l += abs(left-A[index_r])
			else:
				ans_l += abs(right-A[index_r])
			index_r -= 1
		else: break
	else:
		if index_r - index_l >= 1:
			if abs(left-A[index_l])+abs(right-A[index_l+1]) > abs(right-A[index_l])+abs(left-A[index_l+1]):
				ans_l += abs(left-A[index_l])+abs(right-A[index_l+1])
				left = A[index_l]
				right = A[index_l+1]
			else:
				ans_l += abs(right-A[index_l])+abs(left-A[index_l+1])
				left = A[index_l+1]
				right = A[index_l]
			index_l += 2
		elif index_r - index_l == 0:
			if abs(left-A[index_r]) > abs(right-A[index_r]):
				ans_l += abs(left-A[index_r])
			else:
				ans_l += abs(right-A[index_r])
			index_l += 1
		else:
			break
	count += 1

A.reverse()

right = A[0]
left = A[0]
index_l = 1
index_r = len(A)-1
ans_r = 0
count = 1
while(1):
	if count % 2 == 1:
		if index_r - index_l >= 1:
			if abs(left-A[index_r])+abs(right-A[index_r-1]) > abs(right-A[index_r])+abs(left-A[index_r-1]):
				ans_r += abs(left-A[index_r])+abs(right-A[index_r-1])
				left = A[index_r]
				right = A[index_r-1]
			else:
				ans_r += abs(right-A[index_r])+abs(left-A[index_r-1])
				left = A[index_r-1]
				right = A[index_r]
			index_r -= 2
		elif index_r - index_l == 0:
			if abs(left-A[index_r]) > abs(right-A[index_r]):
				ans_r += abs(left-A[index_r])
			else:
				ans_r += abs(right-A[index_r])
			index_r -= 1
		else: break
	else:
		if index_r - index_l >= 1:
			if abs(left-A[index_l])+abs(right-A[index_l+1]) > abs(right-A[index_l])+abs(left-A[index_l+1]):
				ans_r += abs(left-A[index_l])+abs(right-A[index_l+1])
				left = A[index_l]
				right = A[index_l+1]
			else:
				ans_r += abs(right-A[index_l])+abs(left-A[index_l+1])
				left = A[index_l+1]
				right = A[index_l]
			index_l += 2
		elif index_r - index_l == 0:
			if abs(left-A[index_r]) > abs(right-A[index_r]):
				ans_r += abs(left-A[index_r])
			else:
				ans_r += abs(right-A[index_r])
			index_l += 1
		else:
			break
	count += 1

		
print(max(ans_l,ans_r))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
a = [0]*N
for i in range(N):
    A = int(input())
    a[i] = A
a.sort()
c = a.copy()
c.reverse()
a = deque(a)
b = [0]*(N-1)
for i in range(N-1):
    if i%2==0:
        b[i]=a.pop()
    else:
        b[i]=a.popleft()
 
ans1 = 0
for i in range(N-2):
    ans1 += abs(b[i+1]-b[i])
ans1 += max(abs(a[0]-b[0]),abs(a[0]-b[-1]))
 
 
 
 
c = deque(c)
b = [0]*(N-1)
for i in range(N-1):
    if i%2==0:
        b[i]=c.pop()
    else:
        b[i]=c.popleft()
 
ans2 = 0
for i in range(N-2):
    ans2 += abs(b[i+1]-b[i])
ans2 += max(abs(c[0]-b[0]),abs(c[0]-b[-1]))
 
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for _ in range(n)]
if n%2==1:
  a=sorted(a)
  res=abs(2*(sum(a[:n//2])-sum(a[n//2:]))+a[n//2]+a[n//2+1])

  a=a[::-1]
  res=max(res,abs(2*(sum(a[:n//2])-sum(a[n//2:]))+a[n//2]+a[n//2+1]))
else:
  a=sorted(a)
  res=abs(2*(sum(a[:n//2])-sum(a[n//2:]))+a[n//2]-a[n//2-1])
print(res)

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
A = sorted(int(input()) for _ in range(N))

def helper(L):
  s = abs(L[N//2] - L[0])

  for i in range((N+1)//2 - 1):
    s += abs(L[-i-1] - L[i])
    s += abs(L[-i-1] - L[i+1])
  if N % 2 == 1:
    s -= abs(L[N//2 + 1] - L[N//2])
  return s

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

Submission status: Accepted

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

def f(a, offset=0):
    global n
    ans = 0
    # if len(a) % 2 == 0:
    #     last = a[0]
    # else:
    init = min(n // 2 + offset, n - 1)
    last = a[init]
    for i in range(n - 1):
        j = i // 2 if i % 2 == 0 else n - 1 - i // 2
        if j == init:
            break
        ans += abs(a[j] - last)
        last = a[j]
    return ans

# print(f(sorted(a)))
# print(f(sorted(a, reverse=True)))
a = sorted(a)
arev = sorted(a, reverse=True)
print(max(
    f(a),
    f(arev),
    f(a, offset = 1),
    f(arev, offset = 1),
))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def main():
	n = int(input())
	lst = []
	for _ in range(n):
		lst += [int(input())]
	lst.sort()
	ylst = lst[::-1]
	ans = 0
	if n % 2 == 1:
		pib = int((n-1)/2)
		for i in range(n):
			ans += 2 * abs(lst[i]-lst[pib])
		print(ans - min(abs(lst[pib-1]-lst[pib]), abs(lst[pib]-lst[pib+1])))
	elif n == 2:
		print(lst[1]-lst[0])
	else:
		pib = int(n/2) - 1
		for i in range(pib):
			ans += abs(lst[i] - lst[pib]) * 2
			ans += abs(ylst[i] - ylst[pib]) * 2
		ans += abs(lst[pib] - ylst[pib]) * (n-1)
		print(ans)
	return

main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

a.sort()

#print(a)    


ans=0

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

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for _ in range(n)]
a.sort()
if n%2==0:
    res=[]
    z=[a[n//2-1]]
    for i in range(n//2-1):
        z.append(a[-i-1])
        z.append(a[n//2-i-2])
    z.append(a[n//2])
    res.append(z)
    
    z=[a[n//2-1]]
    for i in range(n//2-1):
        z.append(a[-i-1])
        z.append(a[i])
    z.append(a[n//2])
    res.append(z)
    
    z=[a[n//2-1]]
    for i in range(n//2-1):
        z.append(a[n//2+i])
        z.append(a[n//2-i-2])
    z.append(a[-1])
    res.append(z)
    
    z=[a[n//2-1]]
    for i in range(n//2-1):
        z.append(a[n//2+i])
        z.append(a[i])
    z.append(a[-1])
    res.append(z)
    
    z=[a[n//2-1]]
    for i in range(n//2-1):
        z.append(a[n//2-i-2])
        z.append(a[-i-1])
    z.append(a[n//2])
    res.append(z)
    
    z=[a[n//2-1]]
    for i in range(n//2-1):
        z.append(a[i])
        z.append(a[-i-1])
    z.append(a[n//2])
    res.append(z)
    
    z=[a[n//2-1]]
    for i in range(n//2-1):
        z.append(a[n//2-i-2])
        z.append(a[n//2+i])
    z.append(a[-1])
    res.append(z)
    
    z=[a[n//2-1]]
    for i in range(n//2-1):
        z.append(a[i])
        z.append(a[n//2+i])
    z.append(a[-1])
    res.append(z)
    
    ans=[]
    for z in res:
        t=0
        for i in range(1,n):
            t+=abs(z[i]-z[i-1])
        ans.append(t)
    print(max(ans))
else:
    res=[]
    z=[a[n//2]]
    for i in range(n//2):
        z.append(a[-i-1])
        z.append(a[i])
    res.append(z)
    
    z=[a[n//2]]
    for i in range(n//2):
        z.append(a[n//2+1+i])
        z.append(a[i])
    res.append(z)
    
    z=[a[n//2]]
    for i in range(n//2):
        z.append(a[-i-1])
        z.append(a[n//2-i-1])
    res.append(z)
    
    z=[a[n//2]]
    for i in range(n//2):
        z.append(a[-i-1])
        z.append(a[i])
    res.append(z)
    
    z=[a[n//2]]
    for i in range(n//2):
        z.append(a[i])
        z.append(a[-i-1])
    res.append(z)
    
    z=[a[n//2]]
    for i in range(n//2):
        z.append(a[i])
        z.append(a[n//2+1+i])
    res.append(z)
    
    z=[a[n//2]]
    for i in range(n//2):
        z.append(a[n//2-i-1])
        z.append(a[-i-1])
    res.append(z)
    
    z=[a[n//2]]
    for i in range(n//2):
        z.append(a[i])
        z.append(a[-i-1])
    res.append(z)
    
    ans=[]
    for z in res:
        t=0
        for i in range(1,n):
            t+=abs(z[i]-z[i-1])
        ans.append(t)
    print(max(ans))

Submission status: Accepted

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

A.sort()
mn = A[:N//2]
mx = A[N//2:][::-1]

C = [0]*N
C[0] = mx[-1]
mxi,mni = 0,0
for i in range(1,N):
    if mxi != mni:
        C[i] = mx[mxi]
        mxi += 1
    else:
        C[i] = mn[mni]
        mni += 1
s = 0
for i in range(N-1):
    s += abs(C[i+1]-C[i])


if N % 2 == 1:
    D = [0]*N
    D[0] = mx[-1]
    mxi,mni = 0,0
    for i in range(1,N):
        if mxi != mni:
            D[i] = mn[mni]
            mni += 1
        else:
            D[i] = mx[mxi]
            mxi += 1
    s2 = 0
    for i in range(N-1):
        s2 += abs(D[i+1]-D[i])
    print(max(s,s2))

else:
    print(s)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = []
for _ in range(N):
  A.append(read())

A.sort()
ans = A[N-1] - A[0]
l = 1; r = N-2
while l < r:
  ans += A[r+1] - A[l] + A[r] - A[l-1]
  l += 1
  r -= 1
if l == r:
  ans += max(A[l+1] - A[l], A[l] - A[l-1])
print(ans)

Submission status: Accepted

Solution code:
def bigger(a,b):
    if a>=b:
        return a
    else:
        return b

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

a.sort()
ans = a[-1] - a[0]
count = 2

left = a[0]
right = a[-1]

hidari = 1
migi = n-2
for i in range(n-2):
    if bigger(abs(left-a[hidari]),abs(left-a[migi])) >= bigger(abs(right-a[hidari]),abs(right-a[migi])):
        ans += bigger(abs(left-a[hidari]),abs(left-a[migi]))
        if abs(left-a[hidari]) > abs(left-a[migi]):
            left = a[hidari]
            hidari += 1
        else:
            left = a[migi]
            migi -= 1
    else:
        ans += bigger(abs(right-a[hidari]),abs(right-a[migi]))
        if abs(right-a[hidari]) > abs(right-a[migi]):
            right = a[hidari]
            hidari += 1
        else:
            right = a[migi]
            migi -= 1
print(ans)

Submission status: Accepted

Solution code:
import itertools


def main():
    n = int(input())

    a = []
    for i in range(n):
        a.append(int(input()))
    a.sort()
    if n == 2:
        print(abs(a[0] - a[1]))
        return
    if n == 3:
        tmp1 = abs(a[0] - a[1]) + abs(a[0] - a[2])
        tmp2 = abs(a[0] - a[2]) + abs(a[1] - a[2])
        print(max([tmp1, tmp2]))
        return
    if n < 10:
        ans = 0
        for a in itertools.permutations(a):
            tmp = 0
            for i in range(len(a) - 1):
                tmp += abs(a[i] - a[i + 1])
            ans = max([ans, tmp])
        print(ans)
        return
    ret1 = a[:n // 2 + (1 if n % 2 == 1 else 0)]
    ret2 = a[n // 2 + (1 if n % 2 == 1else 0):]
    ret1 = [ret1[-1]] + ret1[:-2] + [ret1[-2]]
    ret2 = ret2[1:] + [ret2[0]]
    ans = 0

    ans += abs(ret1[-1] - ret2[-1])
    for i in range(len(ret2) - 1):
        ans += abs(ret1[i] - ret2[i])
        ans += abs(ret1[i + 1] - ret2[i])
    if len(ret1) != len(ret2):
        ans += abs(ret1[-2] - ret2[-1])

    if n % 2 == 0:
        print(ans)
        return
    ans1 = ans

    ret1 = a[:n // 2 + (0 if n % 2 == 1 else 1)]
    ret2 = a[n // 2 + (0 if n % 2 == 1else 1):]
    # ret1 = ret1[1:] + [ret1[0]]
    ret2 = [ret2[0]] + ret2[2:] + [ret2[1]]
    ans = 0

    ans += abs(ret1[-1] - ret2[-1])
    for i in range(len(ret1) - 1):
        ans += abs(ret2[i] - ret1[i])
        ans += abs(ret2[i + 1] - ret1[i])
    if len(ret1) != len(ret2):
        ans += abs(ret1[-1] - ret2[-2])
    print(max([ans, ans1]))


main()

Submission status: Accepted

Solution code:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline
mii=lambda:map(int,input().split())

n=int(input())
a=[int(input()) for _ in range(n)]
a.sort()

b=[]
i=0
j=len(a)-1
test=10**9
while j-i>=1:
    b.append(a[i])
    b.append(a[j])
    i+=1
    j-=1
if i==j:
    for k in b:
        test=min(test,abs(k-a[i]))
    b.append(a[i])


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




print(sum(ans)-min(ans+[test]))

Submission status: Accepted

Solution code:
n = int(input())

a = [0] * n

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

a.sort()

r =[ 0] * len(a)

r[0] = a[(  n-1) // 2]

pr = 1
pi=0
pj=len(a)-1



while pr <len(a):
    r[pr] = a[pj]
    pr += 1
    pj -= 1
    if pr >=len(a):
        break
    r[pr] = a[pi]
    pr += 1
    pi += 1

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

pr = 1
pi=0
pj=len(a)-1

while pr <len(a):
    r[pr] = a[pi]
    pr += 1
    pi += 1

    if pr >=len(a):
        break
    r[pr] = a[pj]
    pr += 1
    pj -= 1

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

result = result1 if result1 > result2 else result2

print(result)

Submission status: Accepted

Solution code:
N = int(raw_input())
a = []
b = []
for i in range(N):
  a.append(int(raw_input()))
a.sort()
if N%2==0:
  b.append(a[N/2-1])
  for i in range(N/2-1):
    b.append(a[N-1-i])
    b.append(a[i])
  b.append(a[N/2])
else:
  if abs(a[(N-1)/2]-a[(N-3)/2])<abs(a[(N-1)/2]-a[(N+1)/2]):
    b.append(a[(N-3)/2])
    a.pop((N-3)/2)
    for i in range((N-1)/2):
      b.append(a[N-i-2])
      b.append(a[i])
  else:
    b.append(a[(N+1)/2])
    a.pop((N+1)/2)
    for i in range((N-1)/2):
      b.append(a[i])
      b.append(a[N-i-2])
x = 0
for i in range(N-1):
  x += abs(b[i+1]-b[i])
print x

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
A.sort()
if N % 2 == 0:
	print(-2*sum(A[:N//2-1]) + 2*(sum(A[N//2+1:])) + A[N//2] - A[N//2-1])
	exit()

a = 2*sum(A[N//2+1:]) - 2*sum(A[:N//2-1]) - A[N//2] - A[N//2-1]
b = 2*sum(A[N//2+2:]) - 2*sum(A[:N//2]) + A[N//2] + A[N//2+1]
print(max(a,b))

Submission status: Accepted

Solution code:
from collections import deque

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

A.sort()

deq = deque()
for a in A:
    deq.append(a)

ans1 = 0
left = right = deq.pop()
flag = 1
while len(deq) >= 2:
    if flag:
        l, r = deq.popleft(), deq.popleft()
    else:
        l, r = deq.pop(), deq.pop()
    ans1 += abs(left + right - l - r)
    flag ^= 1
    left, right = l, r
if len(deq):
    v = deq.pop()
    ans1 += max(abs(left - v), abs(right - v))

deq = deque()
for a in A:
    deq.append(a)

ans2 = 0
left = right = deq.popleft()
flag = False
while len(deq) >= 2:
    if flag:
        l, r = deq.popleft(), deq.popleft()
    else:
        l, r = deq.pop(), deq.pop()
    flag ^= 1
    ans2 += abs(left + right - l - r)
    left, right = l, r
if len(deq):
    v = deq.pop()
    ans2 += max(abs(left - v), abs(right - v))

print(max(ans1, ans2))

Submission status: Accepted

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

data.sort()

small = data[:len(data)//2]
large = data[len(data)//2:]

if N>4:
    large = [large[0]]+large[2:]+[large[1]]

ndata = []
pos = 0
if N%2==0:
    while pos < len(small):
        ndata.append(large[pos])
        ndata.append(small[pos])
        pos += 1
else:
    while pos < len(small):
        ndata.append(large[pos])
        ndata.append(small[pos])
        pos += 1
    ndata.append(large[pos])

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

if N%2 == 0:
    summ2 = summ1
else:
    small = data[:len(data)//2+1]
    large = data[len(data)//2+1:]
    if N>4:
        small = [small[-1]]+small[:-2]+[small[-2]]
    ndata = []
    pos = 0
    while pos < len(large):
        ndata.append(small[pos])
        ndata.append(large[pos])
        pos += 1
    ndata.append(small[pos])
    summ2 = 0
    for i in range(N-1):
        summ2 += abs(ndata[i]-ndata[i+1])

print(max(summ1,summ2))

Submission status: Accepted

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

l = a[0]
r = a[0]
ixl = 1
ixr = n-1

s = 0
d = -1

while ixl < ixr:
    if d == 1:
        nl = a[ixl]
        nr = a[ixl+1]
        ixl += 2
    else:
        nl = a[ixr]
        nr = a[ixr-1]
        ixr -= 2
    s += ((l+r)-(nl+nr))*d
    l = nl
    r = nr
    d *= -1
if ixl == ixr:
    s += (l-a[ixl])*d
s1 = s

a.reverse()

l = a[0]
r = a[0]
ixl = 1
ixr = n-1

s = 0
d = 1

while ixl < ixr:
    if d == -1:
        nl = a[ixl]
        nr = a[ixl+1]
        ixl += 2
    else:
        nl = a[ixr]
        nr = a[ixr-1]
        ixr -= 2
    s += ((l+r)-(nl+nr))*d
    l = nl
    r = nr
    d *= -1
if ixl == ixr:
    s += (l-a[ixl])*d
s = max(s, s1)

print(s)

Submission status: Accepted

Solution code:
import collections


def in_place_solve(n, bs):
    bs.sort()
    xs = collections.deque((bs[0], bs[n - 1]))
    i = 1
    j = n - 2
    while i < j:
        left = bs[i]
        right = bs[j]
        cs = (abs(xs[0] - left), abs(xs[-1] - left), abs(xs[0] - right), abs(xs[-1] - right))
        m = max(cs)
        if m == cs[0]:
            xs.appendleft(left)
            i += 1
        elif m == cs[1]:
            xs.append(left)
            i += 1
        elif m == cs[2]:
            xs.appendleft(right)
            j -= 1
        else:
            xs.append(right)
            j -= 1
    if i == j:
        rest = bs[i]
        if abs(xs[0] - rest) >= abs(xs[-1] - rest):
            xs.appendleft(rest)
        else:
            xs.append(rest)
    ys = list(xs)
    s = sum(abs(yj - yi) for yi, yj in zip(ys[:-1], ys[1:]))
    return s


def main():
    n = int(input())
    bs = [int(input()) for _ in range(n)]
    print(in_place_solve(n, bs))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A=[int(input()) for x in range(N)]

    A.sort()
    s = 0
    e = N - 1
    L = A[0]
    R = A[e]
    ret1 = R - L
    while True:
        ss = s + 1
        ee = e - 1

        b = max(abs(L - A[ss]), abs(R - A[ss])) > max(abs(L - A[ee]), abs(R - A[ee]))

        if b:
            s += 1
            if abs(L - A[s]) < abs(R - A[s]):
                ret1 += abs(R - A[s])
                R = A[s]
            else:
                ret1 += abs(L - A[s])
                L = A[s]
        else:
            e -= 1
            if s == e: break
            if abs(L - A[e]) < abs(R - A[e]):
                ret1 += abs(R - A[e])
                R = A[e]
            else:
                ret1 += abs(L - A[e])
                L = A[e]
        if s == e: break

    # 出力
    print("{}".format(ret1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    A = sorted([int(input()) for _ in (None,)*N])
    if N == 1:
        return str(0)
    if N == 2:
        return str(abs(A[0]-A[1]))
    m = -(N>>1)
    b = N&1
    c1 = 2*sum(A[m+(1-b):]) - sum(A[m-1-b:m]) - 2*sum(A[:m-1-b]) + (1-b)*A[m]
    A = A[::-1]
    c2 = -2*sum(A[m+(1-b):]) + sum(A[m-1-b:m]) + 2*sum(A[:m-1-b]) - (1-b)*A[m]
    return str(max(c1,c2))

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
A=[]
for i in range(N):
    s=int(input())
    A.append(s)
A.sort()
H=deque()
H.append(A[0])
s=1
t=N-1
i=0
while t-s!=-1:
    x=A[s]
    y=A[t]
    a=abs(H[0]-x)
    b=abs(H[-1]-x)
    c=abs(H[0]-y)
    d=abs(H[-1]-y)
    e=max(a,b,c,d)
    if a==e:
        H.appendleft(x)
        s+=1
    elif b==e:
        H.append(x)
        s+=1
    elif c==e:
        H.appendleft(y)
        t-=1
    else:
        H.append(y)
        t-=1
ans=0
for i in range(N-1):
    ans+=abs(H[i+1]-H[i])
print(ans)

Submission status: Accepted

Solution code:
N, = [int(i) for i in input().split(' ')]
import sys
As = []
for line in sys.stdin:
    As.append(int(line.strip()))

As = sorted(As)
r = 0
r2 = 0
if N == 2:
    r = As[1] - As[0]
elif N == 3:
    r = max(2*As[2] - As[1] - As[0], As[2] + As[1] - 2 * As[0])
elif N % 2 == 1:
    r -= sum(As[:(N//2) - 1]) * 2
    r -= As[(N // 2)] + As[(N // 2) - 1]
    r += sum(As[(N // 2)+1:]) * 2
    #print(r)

    r2 -= sum(As[:(N//2)]) * 2
    r2 += As[(N // 2)+1] + As[(N // 2)]
    r2 += sum(As[(N // 2)+2:]) * 2
    #print(r2)
    r = max(r, r2)
else:
    #print(As[:(N//2) - 1])
    r -= sum(As[:(N//2) - 1]) * 2
    r += As[(N // 2)] - As[(N // 2) - 1]
    r += sum(As[(N // 2)+1:]) * 2
    #r2 -= sum(As[:(N//2)]) * 2
    #r2 += As[(N // 2)+1] + As[(N // 2)]
    #r2 += sum(As[(N // 2)+2:]) * 2
    #r = max(r, r2)
print(r)

Submission status: Accepted

Solution code:
n = int(input())

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

a.sort()

i = 1
j = n - 1
ans = 0
comp = [a[0], a[0]]
for _ in range(n - 1):
    if comp[1] - a[i] >= a[j] - comp[0]:
        ans += comp[1] - a[i]
        comp[1] = a[i]
        i += 1
    else:
        ans += a[j] - comp[0]
        comp[0] = a[j]
        j -= 1
    comp.sort()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort()
gap = a[n-1] - a[0]
for i in range(1,n // 2):
    gap += a[-(i + 1)] - a[i - 1]
    gap += a[-i] - a[i]
if len(a) % 2 == 1:
    gap += max(a[n//2] - a[n//2 - 1], a[n//2 + 1] - a[n//2])
print(gap)

Submission status: Accepted

Solution code:
import math
n = int(input())
lis = [int(input()) for i in range(n)]
lis.sort()
ans = 0
if n % 2 == 0:
  lisa = lis[:n//2]
  lisb = lis[n//2:]
  lia = []
  lib = []
  lic = []
  lid = []
  for i in range(n//2):
    lia.append(lisa[i])
    lib.append(lisb[i])
    lic.append(lisa[i])
    lid.append(lisb[-(i+1)])
    lia.append(lisb[i])
    lib.append(lisa[i])
    lic.append(lisb[-(i+1)])
    lid.append(lisa[i])
  coa = 0
  cob = 0
  coc = 0
  cod = 0
  for i in range(n-1):
    coa += abs(lia[i+1]-lia[i])
    cob += abs(lib[i+1]-lib[i])
    coc += abs(lic[i+1]-lic[i])
    cod += abs(lid[i+1]-lid[i])
  print(max(coa,cob,coc,cod))
else:
  lia = [lis[(n-1)//2]]
  lib = [lis[(n-1)//2]]
  lic = [lis[(n-1)//2]]
  lid = [lis[(n-1)//2]]
  lis.remove(lis[(n-1)//2])
  lisa = lis[:n//2]
  lisb = lis[n//2:]
  for i in range(n//2):
    lia.append(lisa[i])
    lib.append(lisb[i])
    lic.append(lisa[i])
    lid.append(lisb[-(i+1)])
    lia.append(lisb[i])
    lib.append(lisa[i])
    lic.append(lisb[-(i+1)])
    lid.append(lisa[i])
  coa = 0
  cob = 0
  coc = 0
  cod = 0
  for i in range(n-1):
    coa += abs(lia[i+1]-lia[i])
    cob += abs(lib[i+1]-lib[i])
    coc += abs(lic[i+1]-lic[i])
    cod += abs(lid[i+1]-lid[i])
  print(max(coa,cob,coc,cod))

Submission status: Accepted

Solution code:
from collections import deque


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

    a.sort()

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

    b_lst = list(b)
    ans = 0
    for i in range(n-2):
        ans += abs(b_lst[i+1]-b_lst[i])

    if n % 2:
        ans += max(abs(a[n//2]-b[0]), abs(a[n//2]-b[-1]))
    else:
        ans += abs(b[n-1]-b[n-2])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for n in range(N)]

A.sort()

res = 0
s = 0
t = N - 1
a = A[s]
b = A[t]
res += b - a
for n in range((N - 1) // 2):
    if s + 1 != t - 1:
        a_2 = A[s + 1]
        b_2 = A[t - 1]
        if b - a_2 <= b_2 - a and b - a_2 <= b_2 - a_2:
            res += b_2 * 2- a - a_2
            a = A[s + 1]

        elif b - a_2 > b_2 - a and b_2 - a <= b_2 - a_2:
            res += b_2 - a_2 * 2 + b
            b = A[t - 1]

        else:
            res += b - a_2 + b_2 - a
            a = A[s + 1]
            b = A[t - 1]

        s += 1
        t -= 1
    else:
        c = A[s + 1]
        res += max(b - c, c - a)

print(res)

Submission status: Accepted

Solution code:

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


A.sort()

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

Submission status: Accepted

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

Submission status: Accepted

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

if n == 2:
	print(abs(a[0] - a[1]))
elif n == 3:
	print(max(abs(a[0] - a[1]) + abs(a[0] - a[2]), abs(a[1] - a[2]) + abs(a[1] - a[0]), abs(a[2] - a[1]) + abs(a[2] - a[0])))
else:
	b = sorted(a)
	ans = [0] * n
	if n % 2 == 0:
		for i in range(2, n-1, 2):
			ans[i] =  b[(i // 2) - 1]
			#print(i, ans[i])
		for i in range(1, n-1, 2):
			ans[i] = b[-1 - ((i - 1) // 2)]
			#print(i, ans[i])
		ans[0] = b[n // 2 - 1]
		ans[n-1] = b[n // 2]
	else:
		ans[0] = b[n // 2]
		if b[n // 2 + 1] + b[n // 2 - 1] >= 2 * b[n // 2]:
			for i in range(2, n-1, 2):
				ans[i] =  b[(i // 2) - 1]
			for i in range(1, n-1, 2):
				ans[i] = b[-1 - ((i - 1) // 2)]

			ans[n-1] = b[n // 2 - 1]
			#ans[n-2] = b[n // 2 + 1]
		else:
			for i in range(1, n-1, 2):
				ans[i] =  b[((i - 1) // 2)]
			for i in range(2, n-1, 2):
				ans[i] = b[-1 - ((i - 2) // 2)]

			ans[n-1] = b[n // 2 + 1]
			#ans[n-2] = b[n // 2 - 1]

	#print(ans)
	print(sum([abs(ans[i] - ans[i+1]) for i in range(n-1)]))

Submission status: Accepted

Solution code:
N = int(input())

A = []
for i in range(N):
    A.append(int(input()))
    
Amin = sorted(A)
Amax = sorted(A,reverse=True)

if N%2==0:
    SUM = 0
    SUM += sum(Amax[:N//2-1])*2
    SUM += sum(Amax[N//2-1:N//2])
    SUM -= sum(Amax[N//2:N//2+1])
    SUM -= sum(Amax[N//2+1:N])*2
    print(SUM)
else:
    SUM_A,SUM_B = 0,0
    #並べ方が2通り
    SUM_A += sum(Amax[:N//2])*2
    SUM_A -= sum(Amax[N//2:N//2+2])
    SUM_A -= sum(Amax[N//2+2:N])*2
    
    SUM_B -= sum(Amin[:N//2])*2
    SUM_B += sum(Amin[N//2:N//2+2])
    SUM_B += sum(Amin[N//2+2:N])*2
    
    print(max([SUM_A,SUM_B]))

Submission status: Accepted

Solution code:
n = int(input())
aa = sorted([int(input()) for i in range(n)])

start = 1
end = n - 1

left = aa[0]
right = aa[0]

ans = 0

while start <= end:
    s = [abs(left - aa[start]), abs(right - aa[start]), abs(left - aa[end]), abs(right - aa[end])]
    if s[0] >= max(s[1], s[2], s[3]):
        left = aa[start]
        start += 1
    elif s[1] >= max(s[2], s[3], s[0]):
        right = aa[start]
        start += 1
    elif s[2] >= max(s[3], s[0], s[1]):
        left = aa[end]
        end -= 1
    elif s[3] >= max(s[0], s[1], s[2]):
        right = aa[end]
        end -= 1
    ans += max(s)

print(ans)