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: Time Limit Exceeded

Solution code:
'''input
3
5
5
1
'''
from sys import exit
n = input()
arr = [input() for i in range(n)]
arr.sort()
if n == 2:
	print abs(arr[0]-arr[1])
	exit(0)

ans = [-1]*(n)
j = 2
for i in range(4,n,2):
	ans[i] =arr[j]
	j += 1
# print ans
j = -2
for i in range(3,n,2):
	ans[i] = arr[j]
	j -= 1
ans[0] = arr[1]
ans[1] = arr[-1]
ans[2] = arr[0]
answ1 = 0
# print ans
for i in range(n-1):
	answ1 += abs(ans[i]-ans[i+1])
answ1 = max(answ1,answ1-abs(ans[-1]-ans[-2])+abs(ans[-1]-ans[0]))

arr.sort(reverse = True)

ans = [-1]*(n)
j = 2
for i in range(4,n,2):
	ans[i] =arr[j]
	j += 1
# print ans
j = -2
for i in range(3,n,2):
	ans[i] = arr[j]
	j -= 1
ans[0] = arr[1]
ans[1] = arr[-1]
ans[2] = arr[0]
answ = 0
# print ans
for i in range(n-1):
	answ += abs(ans[i]-ans[i+1])
answ = max(answ,answ-abs(ans[-1]-ans[-2])+abs(ans[-1]-ans[0]))
print max(answ,answ1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
A.sort()
ary1 = [A[0]]
ary2 = [A[N-1]]
fst = 0
lst = N
fst_flg = False
sum1, sum2 = 0,0
while fst + 1 < lst:
	if fst_flg:
		fst_flg = False
		if fst + 2 != lst:
			fst += 1
			ary1 = [A[fst]] + ary1 + [A[fst+1]]
			ary2 = [A[N-1-fst]] + ary2 + [A[N-1-fst-1]]
			fst += 1
			l = len(ary1)
			sum1 += abs(ary1[0]-ary1[1]) + abs(ary1[l-1]-ary1[l-2])
			sum2 += abs(ary2[0]-ary2[1]) + abs(ary2[l-1]-ary2[l-2])
		else:
			fst += 1
			ary1 = [A[fst]] + ary1
			ary2 = [A[N-1-fst]] + ary2
			sum1 += abs(ary1[0]-ary1[1])
			sum2 += abs(ary2[0]-ary2[1])
	else:
		fst_flg = True
		if fst + 2 != lst:
			lst -= 1
			ary1 = [A[lst]] + ary1 + [A[lst-1]]
			ary2 = [A[N-1-lst]] + ary2 + [A[N-lst]]
			lst -= 1
			l = len(ary1)
			sum1 += abs(ary1[0]-ary1[1]) + abs(ary1[l-1]-ary1[l-2])
			sum2 += abs(ary2[0]-ary2[1]) + abs(ary2[l-1]-ary2[l-2])
		else:
			lst -= 1
			ary1 = [A[lst]] + ary1
			ary2 = [A[N-1-lst]] + ary2
			sum1 += abs(ary1[0]-ary1[1])
			sum2 += abs(ary2[0]-ary2[1])
print(max(sum1,sum2))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
A.sort()
ary1 = [A[0]]
ary2 = [A[N-1]]
fst = 0
lst = N
fst_flg = False
while fst + 1 < lst:
	if fst_flg:
		fst_flg = False
		if fst + 2 != lst:
			fst += 1
			ary1 = [A[fst]] + ary1 + [A[fst+1]]
			ary2 = [A[N-1-fst]] + ary2 + [A[N-1-fst-1]]
			fst += 1
		else:
			fst += 1
			ary1 = [A[fst]] + ary1
			ary2 = [A[N-1-fst]] + ary2
	else:
		fst_flg = True
		if fst + 2 != lst:
			lst -= 1
			ary1 = [A[lst]] + ary1 + [A[lst-1]]
			ary2 = [A[N-1-lst]] + ary2 + [A[N-lst]]
			lst -= 1
		else:
			lst -= 1
			ary1 = [A[lst]] + ary1
			ary2 = [A[N-1-lst]] + ary2
sum1,sum2=0,0
for i in range(N-1):
	sum1 += abs(ary1[i] - ary1[i+1])
	sum2 += abs(ary2[i] - ary2[i+1])
print(max(sum1,sum2))

Submission status: Accepted

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

A.sort()
left = A[0]
right = A[N - 1]
ans = right - left
for i in range((N - 2) // 2):
    if i % 2 == 0:
        ans += right - A[1 + i]
        ans += A[N - 2 - i] - left
        right = A[1 + i]
        left = A[N - 2 - i]
    else:
        ans += left - A[1 + i]
        ans += A[N - 2 - i] - right
        left = A[1 + i]
        right = A[N - 2 - i]

if N % 2 == 1:
    ans += max(abs(right - A[N // 2]), abs(left - A[N // 2]))

print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
ls = [0] * n
for i in range(n):
    ls[i] = int(input())
ls.sort()
# 長さ2なら例外処理する
if n == 2:
    print(abs(ls[0]-ls[1]))
    sys.exit()
if n % 2 == 1:
    # biggerを2つとる方
    smaller = ls[:n//2+1]
    bigger = ls[n//2+1:]
    diff_1 = 2 * sum(bigger) - 2*sum(smaller) + smaller[-1] + smaller[-2]
    # smallerを2つとる方
    smaller = ls[:n//2]
    bigger = ls[n//2:]
    diff_2 = -2 * sum(smaller) + 2 * sum(bigger) - bigger[0] - bigger[1]
    diff = max(diff_1,diff_2)
else:
    smaller = ls[:n//2]
    bigger = ls[n//2:]
    diff = 2 * sum(bigger) - min(bigger) - 2 * sum(smaller) + max(smaller)

print(diff)

Submission status: Accepted

Solution code:
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())
A.sort()
ans = 0
a = 0
b = 0
if (N+1)//2==N//2:
    for i in range(N//2):
        ans -= 2*A[i]
    ans += A[N//2-1]

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

    print(ans)

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

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

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

Submission status: Accepted

Solution code:
N,*a=map(int,open(0))
n=N//2-1
a.sort()
print(2*sum(a[n+2:])-2*sum(a[:n])+a[n+1]-a[n]-N%2*min(a[~n]+a[n],2*a[n+1]))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
As = sorted(A)
lowIdx = 0
highIdx = len(As)-1


l = As[lowIdx]
r = As[highIdx]
diff = r-l
lowIdx+=1
highIdx-=1

while lowIdx <= highIdx:
    low = As[lowIdx]
    high = As[highIdx]
    rHigh = abs(r - As[highIdx])
    lHigh = abs(l - As[highIdx])
    rLow = abs(r - As[lowIdx])
    lLow = abs(l - As[lowIdx])
    if rHigh >= max(lHigh, rLow, lLow):
        diff += rHigh
        r = high
        highIdx -= 1
    elif lHigh >= max(rLow, lLow):
        diff += lHigh
        l = high
        highIdx -= 1
    elif rLow >= lLow:
        diff += rLow
        r = low
        lowIdx += 1
    else:
        diff += lLow
        l = low
        lowIdx += 1

print(diff)

Submission status: Accepted

Solution code:
# tenka1-2018C - Align
def main():
    N, *A = map(int, open(0).read().split())
    A.sort()
    if N & 1:
        low, high, mid = A[: N // 2], A[N // 2 + 1 :], A[N // 2]
        x = (sum(high) - sum(low)) * 2 - mid + low[-1]
        y = (sum(high) - sum(low)) * 2 + mid - high[0]
        ans = max(x, y)
    else:
        low, high = A[: N // 2], A[N // 2 :]
        ans = (sum(high) - sum(low)) * 2 - high[0] + low[-1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    a = sorted([int(input()) for _ in range(n)], reverse=True)
    ans = 0
    center = n // 2

    # See:
    # http://drken1215.hatenablog.com/entry/2018/10/28/222800
    # KeyInsight
    # a > b < c > d < e ...
    # a < b > c < d > e ...の形で決め打ちしてよい
    # それぞれの係数に着目する
    if n % 2 == 0:
        ans += sum(a[:center - 1]) * 2
        ans += a[center - 1]
        ans -= a[center]
        ans -= sum(a[center + 1:]) * 2
    else:
        ans1 = 0
        ans1 += sum(a[:center - 1]) * 2
        ans1 += a[center - 1]
        ans1 += a[center]
        ans1 -= sum(a[center + 1:]) * 2

        ans2 = 0
        ans2 += sum(a[:center]) * 2
        ans2 -= a[center]
        ans2 -= a[center + 1]
        ans2 -= sum(a[center + 2:]) * 2
        ans = max(ans1, ans2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

X = sorted(X)

M = []
m = []
for i in range(N // 2):
	M.append(X[-1 - i])
	m.append(X[i])
M = sorted(M)

if N % 2 == 0:
	n = N
else:
	n = N - 1
s = []
for i in range(n):
	if i % 2 == 0:
		s.append(M[i // 2])
	else:
		s.append(m[i // 2])
ans = 0
for i in range(n - 1):
	ans += abs(s[i + 1] - s[i])
if N % 2 == 1:
	ans += max(abs(X[N // 2] - s[0]), abs(X[N // 2] - s[-1]))
print(ans)

Submission status: Accepted

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

A.sort()

if N%2 == 0:
    l = N//2
    B1 = A[:l]
    B2 = A[l:]
    ans = 0
    for i in range(l):
        ans += (B2[i] - B1[i])*2
    ans -= B2[0] - B1[-1]
    print(ans)
else:
    l = N//2
    B1 = A[:l]
    B2 = A[l:]
    a1 = 0
    for i in range(l):
        a1 -= B1[i]*2
    for i in range(l+1):
        if i == 0 or i == 1:
            a1 += B2[i]
        else:
            a1 += B2[i]*2
    
    C1 = A[:l+1]
    C2 = A[l+1:]
    a2 = 0

    for i in range(l):
        a2 += C2[i]*2
    for i in range(l+1):
        if i == l-1 or i == l:
            a2 -= C1[i]
        else:
            a2 -= C1[i]*2
    print(max(a1, a2))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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 = [ni() for _ in range(n)]

a.sort()

b = a.copy()
c = a.copy()

# 小さい順に詰める
bdeq = deque(b)
bret = deque()

bret.append(bdeq.popleft())
push_small = False
while len(bdeq) > 1:
    if push_small:
        bret.append(bdeq.popleft())
        bret.appendleft(bdeq.popleft())
        push_small = False

    else:
        bret.append(bdeq.pop())
        bret.appendleft(bdeq.pop())
        push_small = True

if len(bdeq) > 0:
    if abs(bdeq[0] - bret[0]) > abs(bdeq[0] - bret[-1]):
        bret.appendleft(bdeq[0])
    else:
        bret.append(bdeq[0])

# 大きい順に詰める
cdeq = deque(c)
cret = deque()

cret.append(cdeq.pop())
push_small = True
while len(cdeq) > 1:
    if push_small:
        cret.append(cdeq.popleft())
        cret.appendleft(cdeq.popleft())
        push_small = False

    else:
        cret.append(cdeq.pop())
        cret.appendleft(cdeq.pop())
        push_small = True

if len(cdeq) > 0:
    if abs(cdeq[0] - cret[0]) > abs(cdeq[0] - cret[-1]):
        cret.appendleft(cdeq[0])
    else:
        cret.append(cdeq[0])

# 答えが大きいほうを選択
bans = 0
for i in range(n-1):
    bans += abs(bret[i] - bret[i+1])

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

print(max(bans, cans))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
a.sort()
x=0;y=0
if n%2==0:
  for i in range(n):
    if i<n//2-1:
      x-=a[i]*2
    elif i==n//2-1:
      x-=a[i]
    elif i==n//2:
      x+=a[i]
    else:
      x+=a[i]*2
  print(x)
else:
  for i in range(n):
    if i<n//2:
      x-=a[i]*2
    elif i==n//2:
      x+=a[i]
    elif i==n//2+1:
      x+=a[i]
    else:
      x+=a[i]*2
  for i in range(n):
    if i<n//2-1:
      y-=a[i]*2
    elif i==n//2-1:
      y-=a[i]
    elif i==n//2:
      y-=a[i]
    else:
      y+=a[i]*2
  print(max(x,y))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
A.sort(reverse=True)
mae=0
ushiro=0
if N%2==0:
    if N>3:
        for i in range(N//2-1):
            mae+=A[i]
        for i in range(N//2+1,N):
            ushiro+=A[i]
    a0=A[N//2-1]
    a1=A[N//2]
    print((mae-ushiro)*2+a0-a1)
else:
    if N>3:
        for i in range(N//2-1):
            mae+=A[i]
        for i in range(N//2+2,N):
            ushiro+=A[i]
    a0=A[N//2-1]
    a1=A[N//2]
    a2=A[N//2+1]
    print((mae-ushiro)*2+max(2*a0-a1-a2,a0+a1-2*a2))

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
A = sorted(A, reverse=True)
L, R = A[0], A[0]
A.pop(0)
num = 0
for i in range(N - 1):
    k1 = A[-1]
    k2 = A[0]
    tmp = []
    tmp.append(abs(L - k1))
    tmp.append(abs(L - k2))
    tmp.append(abs(R - k1))
    tmp.append(abs(R - k2))
    ma = max(tmp)
    if ma == abs(L - k1):
        num += abs(L - k1)
        A.pop(-1)
        L = k1
    elif ma == abs(L - k2):
        num += abs(L - k2)
        A.pop(0)
        L = k2
    elif ma == abs(R - k1):
        num += abs(R - k1)
        A.pop(-1)
        R = k1
    else:
        num += abs(R - k2)
        A.pop(0)
        R = k2

print(num)

Submission status: Accepted

Solution code:
N = int(input())
lis = [int(input()) for n in range(N)]
lis = sorted(lis)
half = len(lis) // 2
low = lis[:half]
high = lis[:half-1:-1]
    

def output(low_lis, high_lis):
    ll, hl = len(low_lis), len(high_lis)
    if ll > hl:
        return calc(low_lis, high_lis)
    return calc(high_lis, low_lis)

def calc(lis1, lis2):
    left = lis1[0]
    right = left
    res = 0
    try:
        for n in range((len(lis1) + 1) // 2):
            res += abs(left - lis1[2*n])
            res += abs(right - lis2[2*n])
            res += abs(lis1[2*n + 1] - lis2[2*n])
            res += abs(lis2[2*n+1] - lis1[2*n])
            right = lis1[2*n + 1]
            left = lis2[2*n+1]
        return res
    except IndexError:
        return res

res1 = output(low, high)
res2 = 0
if len(lis) % 2:
    low = lis[:half + 1]
    high = lis[:half:-1]
    res2 = output(low, high)
    
print(max(res1, res2))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(int(input())for i in range(N))
A.sort()
A = np.array(A)
C1,C2 = [],[]
if N%2 == 1:
    C1 = [-2]*int(N/2-1)+[-1]*2+[2]*int(N/2)
    C2 = [-2]*int(N/2)+[1]*2+[2]*int(N/2-1)
else:
    C1 = [-2]*int(N/2-1)+[-1]+[1]+[2]*int(N/2-1)
    C2 = [-2]*int(N/2-1)+[-1]+[1]+[2]*int(N/2-1)
C1 = np.array(C1)
C2 = np.array(C2)
ans = max(sum(A*C1),sum(A*C2))
print(ans)

Submission status: Accepted

Solution code:
#tenka1PC
#C:Align
import sys
input=sys.stdin.readline
from collections import deque
N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
if N%2==0:
    ans=2*(-1*sum(A[0:N//2])+sum(A[N//2:N]))
    ans+=A[N//2-1]-A[N//2]
elif N%2==1:
    ans=2*(-1*sum(A[0:N//2])+sum(A[1+N//2:N]))
    a1,a2,a3=A[N//2-1],A[N//2],A[N//2+1]
    if 2*a2-a1-a3>=0:
        ans+=a2-a3
    else:
        ans+=a1-a2
print(ans)
#notsub

Submission status: Accepted

Solution code:
# 入力
N = int(input())
A = [int(input()) for _ in range(N)]

B = sorted(A)

# (中央値、最小値, 最大値, 2番目の最小値, 2番目の最大値, ...) の順で差をとる場合と、
# (中央、最大値, 最小値, 2番目の最大値, 2番目の最小値, ...) の順で差をとる場合を比較し、
# 大きい方を解とする
ans = (
    2 * sum(
        B[-(i + 1)] - B[i]
        for i in range(N // 2)
    ) - min(
        B[N // 2] - B[N // 2 - 1],
        B[N // 2 + 1] - B[N // 2] if N % 2 == 1 else 10**18
    )
)
# 出力
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 15 22:46:42 2019

@author: Yamazaki Kenichi
"""
import math
N = int(input())
A = [int(input()) for i in range(N)]

A.sort()

temp1,temp2 = 0,0
if N%2 != 55:
    temp1 += A[-1]+A[-2]-2*A[0]
#    print(temp1,A[-1],A[-2],A[0])
    for i in range(N//2-1):
        temp1 += A[-1-(math.ceil(i/2)*2)] - A[(i//2*2)+1]
        temp1 += A[-2-(math.ceil(i/2)*2)] - A[(i//2*2)+2]
#        print(temp1,-1-(math.ceil(i/2)*2),-2-(math.ceil(i/2)*2),(i//2*2)+1,(i//2*2)+2)
    temp2 += 2*A[-1]-A[0]-A[1]
#    print(temp2,A[-1],A[0],A[1])
    for i in range(N//2-1):
        temp2 += A[-2-(i//2*2)] - A[(math.ceil(i/2)*2)]
        temp2 += A[-3-(i//2*2)] - A[(math.ceil(i/2)*2)+1]
#        print(temp2,-2-(i//2*2),-3-(i//2*2),(math.ceil(i/2)*2),(math.ceil(i/2)*2))
print(max(temp1,temp2))

Submission status: Accepted

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

a = len(A)
if a%2==0:
  answer = 2 * sum(A[a//2+1:]) + A[a//2] - A[a//2-1] - 2* sum(A[:a//2-1])
  
if a%2==1:
  b = a//2
  if 2*A[b] - A[b-1] - A[b+1]<0:
    answer = 2*sum(A[b+1:]) - A[b] - A[b-1] - 2*sum(A[:b-1])
  else:
    answer = A[b] + A[b+1] + 2*sum(A[b+2:]) - 2*sum(A[:b])  
  
print(answer)

Submission status: Accepted

Solution code:
N = input()
a = []
for i in range(N):
	a.append(input())
a.sort()
if(N % 2 == 1):
	print((sum(a[(N+1)/2:])-sum(a[:(N+1)/2-1]))*2-min([a[(N+1)/2-1]-a[(N+1)/2-2],a[(N+1)/2]-a[(N+1)/2-1]]))
else:
	print((sum(a[N/2:])-sum(a[:N/2]))*2-(a[N/2]-a[N/2-1]))

Submission status: Accepted

Solution code:
N = input()
a = []
for i in range(N):
	a.append(input())
a.sort()
if(N % 2 == 1):
	print((sum(a[N/2+1:])-sum(a[:N/2]))*2-min([a[N/2]-a[N/2-1],a[N/2+1]-a[N/2]]))
else:
	print((sum(a[N/2:])-sum(a[:N/2]))*2-(a[N/2]-a[N/2-1]))

Submission status: Accepted

Solution code:
n = int(input())
l = [int(input()) for _ in range(n)]
l.sort()
if n%2:
  s1 = l[:(n-1)//2]
  b1 = l[(n-1)//2:]
  t1 = sum(b1)*2 - sum(s1)*2 -sum(b1[:2])
  s2 = l[:(n+1)//2]
  b2 = l[(n+1)//2:]
  t2 = sum(b2)*2 - sum(s2)*2 + sum(s2[-2:])
  t = max(t1,t2)
else:
  s = l[:n//2]
  b = l[n//2:]
  t = sum(b)*2 - sum(s)*2 -b[0] + s[-1]
print(t)

Submission status: Accepted

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

A=sorted(A)
B=A[:]

ans=0
#小さいのが真ん中
top=A[0]
bottom=A[0]
tmp=0
turn=True
del A[0]
while  A:
  if len(A)==1:
    tmp+=max(abs(top-A[0]),abs(bottom-A[0]))
    break
    pass
  if turn:
    a,b=A[-2],A[-1]
  else:
    a,b=A[0:2]
    
  if abs(a-bottom)+abs(b-top)<abs(a-top)+abs(b-bottom):
    a,b=b,a
  tmp+=abs(a-bottom)+abs(b-top)
  bottom,top=a,b
  if turn:
    del A[-1]
    del A[-1]
  else:
    del A[0]
    del A[0]
  turn=not turn

ans=tmp
A=B
top=A[-1]
bottom=A[-1]
tmp=0
del A[-1]
turn = True
while  A:
  #print("center big:tmp: ", tmp)
  if len(A)==1:
    tmp+=max(abs(top-A[0]),abs(bottom-A[0]))
    break
    pass
  if turn:
    a,b=A[0],A[1]
  else:
    a,b=A[-1],A[-2]
    
  if abs(a-bottom)+abs(b-top)<abs(a-top)+abs(b-bottom):
    a,b=b,a
  tmp+=abs(a-bottom)+abs(b-top)
  bottom,top=a,b
  if turn:
    del A[0] 
    del A[0]
  else:
    del A[-1]
    del  A[-1]
  turn= not turn

ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).readlines())
a.sort()
if n%2:
  b=a[:n//2]
  c=a[n//2:]
  for i in range(n//2):
    b[i]*=2
  for i in range(2,n//2+1):
    c[i]*=2
  m=sum(c)-sum(b)
  b=a[:n//2+1]
  c=a[n//2+1:]
  for i in range(n//2-1):
    b[i]*=2
  for i in range(n//2):
    c[i]*=2
  m=max(m,sum(c)-sum(b))
else:
  b=a[:n//2]
  c=a[n//2:]
  for i in range(n//2-1):
    b[i]*=2
  for i in range(1,n//2):
    c[i]*=2
  m=sum(c)-sum(b)
print(m)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(int(input()) for i in range(n))
median = a[(n-1)//2]
ans = 0
for i in range(n):
    ans += 2*abs(a[i] - median)
if n % 2 == 0:
    ans -= abs(a[(n-1)//2+1] - median)
else:
    ans -= min(abs(a[(n-1)//2+1] - median), abs(a[(n-1)//2-1] - median))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
#import numpy as np
import itertools
n = int(input())
a = []
for i in range(n):
    a.append(input())
# [d1, d2, d3, ..., dN]
a = [int(m) for m in a]

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

Submission status: Accepted

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

if N % 2 == 0:
    X = [-2] * ((N - 2) // 2) + [-1, 1] + [2] * ((N - 2) // 2)
    ans = sum([a * x for a, x in zip(A, X)])
    print(ans)
else:
    X1 = [-2] * ((N - 2) // 2 + 1) + [1, 1] + [2] * ((N - 2) // 2)
    X2 = [-2] * ((N - 2) // 2) + [-1, -1] + [2] * ((N - 2) // 2 + 1)
    ans1 = sum([a * x for a, x in zip(A, X1)])
    ans2 = sum([a * x for a, x in zip(A, X2)])
    print(max(ans1, ans2))

Submission status: Accepted

Solution code:
from itertools import accumulate


class CoeffTable:
    def __init__(self, n):
        self.n = n
        if n == 2:
            (self.p2, self.p1, self.m1, self.m2) = (0, 1, 1, 0)
        if n % 2 == 0:
            self.p1 = self.m1 = 1
            self.p2 = self.m2 = (n - 1) // 2
        else:
            self.p1 = 0
            self.m1 = 2
            self.p2 = (n - 1) // 2
            self.m2 = (n - 2) // 2

    def reverse(self):
        (self.p2, self.p1, self.m1, self.m2) = (
            self.m2,
            self.m1,
            self.p1,
            self.p2,
        )

    def cumsum(self):
        return list(accumulate([self.p2, self.p1, self.m1, self.m2]))



def main(n, seq):
    seq = sorted(seq, reverse=True)
    coeff = CoeffTable(n)
    cm = coeff.cumsum()
    ans1 = (
        2 * sum(seq[0 : cm[0]])
        + 1 * sum(seq[cm[0] : cm[1]])
        - 1 * sum(seq[cm[1] : cm[2]])
        - 2 * sum(seq[cm[2] : cm[3]])
    )
    coeff.reverse()
    rcm = coeff.cumsum()
    ans2 = (
        2 * sum(seq[0 : rcm[0]])
        + 1 * sum(seq[rcm[0] : rcm[1]])
        - 1 * sum(seq[rcm[1] : rcm[2]])
        - 2 * sum(seq[rcm[2] : rcm[3]])
    )
    ans = max(ans1, ans2)
    print(ans)
    return


if __name__ == "__main__":
    n = int(input())
    sample = []
    for _ in range(n):
        sample.append(int(input()))
    main(n, sample)

Submission status: Accepted

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

print(max(ans1,ans2))

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
# Tenka1PC C - Align

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

mult = []
if N % 2 == 0:
    for i in range(N):
        if 0 <= i <= (N//2 - 1) - 1:
            mult.append(2)
        elif i == N // 2 - 1:
            mult.append(1)
        elif i == N // 2:
            mult.append(-1)
        else:
            mult.append(-2)
    ans = sum([a*m for a, m in zip(A, mult)])
else:
    mult1 = []
    mult2 = []
    for i in range(N):
        if 0 <= i <= (N//2 - 1) - 1:
            mult1.append(2)
        elif i == N // 2 - 1:
            mult1.append(1)
        elif i == N // 2:
            mult1.append(1)
        else:
            mult1.append(-2)
    for i in range(N):
        if 0 <= i <= (N//2 - 1):
            mult2.append(2)
        elif i == N // 2:
            mult2.append(-1)
        elif i == N // 2 + 1:
            mult2.append(-1)
        else:
            mult2.append(-2)
    ans = max(sum([a*m for a, m in zip(A, mult1)]), sum([a*m for a, m in zip(A, mult2)]))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a = [int(input()) for _ 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]
else:
    ans1 = sum(a[n//2+1:]) * 2 - sum(a[:n//2+1]) - sum(a[:n//2-1])
    ans2 = sum(a[n//2:]) + sum(a[n//2+2:]) - sum(a[:n//2]) * 2
    ans = max(ans1, ans2)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[int(input()) for _ in range(n)]
l.sort()
m=sorted((-1)**(i+1) if i==0 or i==n-1 else 2*((-1)**(i+1)) for i in range(n))
f=lambda x,y:x*y
a=abs(sum(map(f,l,m)))
b=abs(sum(map(f,l[::-1],m)))
print(max(a,b))

Submission status: Accepted

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

i = 0 ; j = n-1; last = j;
ret = ret2 = 0
diff = 10**9

while i != j:
    last = j
    ret += a[j] - a[i]
    diff = min(diff, a[j] - a[i])
    
    i+=1
    if i==j: break
    last = i
    ret += a[j] - a[i]
    diff = min(diff, a[j] - a[i])

    j-=1
ret += a[last] - a[0]
diff = min(diff, a[last] - a[0])
ret -= diff

i = 0 ; j = n-1; last = j;

while i != j:
    last = i
    ret2 += a[j] - a[i]
    diff = min(diff, a[j] - a[i])
    
    j-=1
    if i==j: break
    last = j
    ret2 += a[j] - a[i]
    diff = min(diff, a[j] - a[i])

    i+=1
ret2 += a[n-1] - a[last]
diff = min(diff, a[n-1] - a[last])
ret2 -= diff

print(max(ret,ret2))

Submission status: Accepted

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

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

Submission status: Accepted

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

A.sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

Submission status: Accepted

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

a = sorted(a)

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

res1 = a[n - 1] + a[n - 2] - (a[0] * 2)
p = n - 3
q = 1
mode = 0
while 1:
    #print(p, q, res1)
    if p < q:
        break
    elif p == q:
        if mode == 0:
            res1 += a[p + 2] - a[p]
        else:
            res1 += a[p] - a[p - 2]
        break
    else:
        if mode == 0:
            res1 += a[p + 1] + a[p + 2] - a[q] - a[q + 1]
            mode = 1
            q += 2
        else:
            res1 += a[p] + a[p - 1] - a[q - 1] - a[q - 2]
            mode = 0
            p -= 2

res2 = a[n - 1] * 2 - a[0] - a[1]
p = n - 2
q = 2
mode = 1
while 1:
    #print(p, q, res2)
    if p < q:
        break
    elif p == q:
        if mode == 0:
            res2 += a[p + 2] - a[p]
        else:
            res2 += a[p] - a[p - 2]
        break
    else:
        if mode == 0:
            res2 += a[p + 1] + a[p + 2] - a[q] - a[q + 1]
            mode = 1
            q += 2
        else:
            res2 += a[p] + a[p - 1] - a[q - 1] - a[q - 2]
            mode = 0
            p -= 2

print(max(res1, res2))

Submission status: Accepted

Solution code:
def f(As):
    Bs = [0] * N

    if N % 2:
        iB, d = 0, N - 1
    else:
        iB, d = 0, N - 2
    for A in As[N//2:]:
        Bs[iB] = A
        iB += d
        if d > 0:
            d = -d + 2
        else:
            d = -d - 2

    if N % 2:
        iB, d = 1, N - 3
    else:
        iB, d = N - 1, -(N - 2)
    for A in reversed(As[:N//2]):
        Bs[iB] = A
        iB += d
        if d > 0:
            d = -d + 2
        else:
            d = -d - 2

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

    return ans


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

As.sort()

print(max(f(As), f(As[::-1])))

Submission status: Accepted

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

"""
N : even
a0 < a1 > a2 ... < aN-1
 -> 2(a1-a2+...-aN-2) - a0 + aN-1
a0 > a1 < a2 ... > aN-1
 -> 2(-a1+a2+...+aN-2) + a0 - aN-1
m = N//2 とすると
(a0, aN-1) = A[m-1], A[m]

N : odd
a0 < a1 > a2 ... > aN-1
 -> 2(a1-a2+...+aN-2) - a0 - aN-1
m = N//2とすると
(a0, aN-1) = A[m-1], A[m]

a0 > a1 < a2 ... < aN-1
 -> 2(-a1+a2-...-aN-2) + a0 + aN-1
m = N//2とすると
(a0, aN-1) = A[m], A[m+1]

"""
ans = 0
m = N // 2

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

Submission status: Accepted

Solution code:
import sys
N=int(input())
A=[int(input()) for i in range(N)]
B=sorted(A)
if N%2==0:
    C=B[:(N//2)]
    D=B[(N//2):]
    print(2*sum(D)-2*sum(C)+C[-1]-D[0])
    sys.exit()
C=B[:(N//2)]
D=B[((N//2)+1):]
s=B[(N//2)]
print(max(2*sum(D)-2*sum(C)+C[-1]-s,2*sum(D)-2*sum(C)+s-D[0]))

Submission status: Accepted

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

A.sort()

B=A[:N//2]
C=A[N//2:]


#print(B)
#print(C)

if len(B)>=2:
    B=[B[-1]]+B[:-2]+[B[-2]]

if len(C)>=2:
    C=[C[1]]+C[2:]+[C[0]]

if N%2==0:
    B,C=C,B



X=[]
b=0
c=0
while b<len(B) or c<len(C):
    if c<len(C):
        X.append(C[c])
    if b<len(B):
        X.append(B[b])
    b+=1
    c+=1

#print(X)
ANS=0
for i in range(1,N):
    ANS+=abs(X[i]-X[i-1])

#print(ANS)




B=A[:N//2+1]
C=A[N//2+1:]

#print(B)
#print(C)

if len(B)>=2:
    B=[B[-1]]+B[:-2]+[B[-2]]

if len(C)>=2:
    C=[C[1]]+C[2:]+[C[0]]

X=[]
b=0
c=0
#print(B)
#print(C)
while b<len(B) or c<len(C):
    if b<len(B):
        X.append(B[b])

    if c<len(C):
        X.append(C[c])

    b+=1
    c+=1

#print(X)
ANS2=0
for i in range(1,N):
    ANS2+=abs(X[i]-X[i-1])

#print(ANS2)

print(max(ANS,ANS2))

Submission status: Accepted

Solution code:
N = int( input())
A = [ int( input()) for _ in range(N)]
ans1 = 0
A.sort()
nowL = A[0]
nowR = A[0]
for i in range(1,N):
    if i%4 == 3:
        ans1 += nowL - A[(i//4)*2+1]
        nowL = A[(i//4)*2+1]
    elif i%4 == 0:
        ans1 += nowR - A[(i//4)*2]
        nowR = A[(i//4)*2]
    elif i%4 == 1:
        ans1 += A[- (i//4)*2-1] - nowL
        nowL = A[-(i//4)*2 - 1]
    else:
        ans1 += A[- (i//4)*2 - 2] - nowR
        nowR = A[-(i//4)*2 - 2]
A = A[::-1]
ans2 = 0
nowL = A[0]
nowR = A[0]
for i in range(1,N):
    if i%4 == 1:
        ans2 += nowL - A[-(i//4)*2-1]
        nowL = A[-(i//4)*2-1]
    elif i%4 == 2:
        ans2 += nowR - A[-(i//4)*2-2]
        nowR = A[-(i//4)*2-2]
    elif i%4 == 3:
        ans2 += A[(i//4)*2+1] - nowL
        nowL = A[(i//4)*2+1]
    else:
        ans2 += A[(i//4)*2] - nowR
        nowR = A[(i//4)*2]

print( max(ans1, ans2))

Submission status: Accepted

Solution code:
N = int(input())
As = [int(input()) for _ in range(N)]

As.sort(reverse=True)

if N % 2:
    ans = 2 * sum(As[:N//2 - 1]) - 2 * sum(As[N//2 + 2:])
    A1, A2, A3 = As[N//2 - 1:N//2 + 2]
    ans += max(A1 + A2 - 2*A3, 2*A1 - A2 - A3)
else:
    ans = 2 * sum(As[:N//2 - 1]) + As[N//2 - 1] - As[N//2] - 2 * sum(As[N//2 + 1:])

print(ans)