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:
N=int(input())
A=[]

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

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = []
for i in range(n):
    lst1.append(int(readline()))
lst1.sort(reverse=True)
if n % 2 == 1:
    minority = n//2
    majority = n - minority
    A = sum(lst1[:minority])*2 - sum(lst1[minority:])*2+sum(lst1[minority:minority+2])
    B = sum(lst1[:majority])*2 - sum(lst1[majority:])*2 - sum(lst1[majority-2:majority])
    ans = max(A, B)
else:
    C = sum(lst1[:n//2])*2 - sum(lst1[n//2:])*2 + lst1[n//2]-lst1[n//2-1]
    D = -C
    ans = max(C, D)
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
n, *a = map(int, read().split())
a.sort()
x = 2*sum(a[(n+1)//2:]) - 2*sum(a[:(n+1)//2])
y = 2*sum(a[n//2:]) - 2*sum(a[:n//2])
if n % 2 == 1:
    x += a[n//2-1] + a[n//2]
    y -= a[n//2] + a[n//2+1]
else:
    x -= a[n//2] - a[n//2-1]
    y -= a[n//2] - a[n//2-1]
    y 
print(max(x, y))

Submission status: Accepted

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

A.sort()
ans = 0
if N % 2 == 0:
    for i in range(N):
        if i < N // 2 - 1:
            ans -= A[i] * 2
        elif i == N // 2 - 1:
            ans -= A[i]
        elif i == N // 2:
            ans += A[i]
        else:
            ans += A[i] * 2
else:
    ans = 0
    for i in range(N):
        if i < N // 2:
            ans -= A[i] * 2
        elif N // 2 <= i <= N // 2 + 1:
            ans += A[i]
        else:
            ans += A[i] * 2
    ans2 = 0
    for i in range(N):
        if i < N // 2 - 1:
            ans2 -= A[i] * 2
        elif N // 2 - 1 <= i <= N // 2:
            ans2 -= A[i]
        else:
            ans2 += A[i] * 2
    # print(ans, ans2)
    ans = max(ans, ans2)
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# 6,8,1,2,3
# 中央値である3から初めて、残りから最大→最小の繰り返しで貪欲に取る
# 3 8 1 6 2
# 最小->最大の順でやるのと両パターン試して、大きい方採用
#
# 3 1 4 1 5 9
# 1 1 3 4 5 9
# 偶数のときは、中央値も2パターン取って大きいのを採用
#
# 5 5 1
# 5 1 5

N=int(input())
A=[0] * N
for i in range(N):
  A[i] = int(input())
  
if N == 2:
  print(abs(A[0] - A[1]))
  exit(0)
  
A=sorted(A)

from collections import deque

def calc(A,first,flip):
  q = deque(A)
  ans = 0
  cur = first
  while q:
    if flip:
      a = q.popleft()
    else:
      a = q.pop()
    ans += abs(a - cur)
    cur = a
    flip^=True
  return ans

if N%2:
  # 奇数のとき
  mid = A.pop(N//2)
  ans1 = calc(A,mid,True)
  ans2 = calc(A,mid,False)
  print(max(ans1,ans2))
  
else:
  # 偶数のとき
  A2 = A.copy()
  mid1 = A.pop(N//2-1)
  ans1_1 = calc(A,mid1,True)
  ans1_2 = calc(A,mid1,False)
  
  mid2 = A2.pop(N//2)
  ans2_1 = calc(A2,mid2,True)
  ans2_2 = calc(A2,mid2,False)
  
  print(max(ans1_1,ans1_2,ans2_1,ans2_2))

Submission status: Accepted

Solution code:
# 6,8,1,2,3
# 中央値である3から初めて、残りから最大→最小の繰り返しで貪欲に取る
# 3 8 1 6 2
# 最小->最大の順でやるのと両パターン試して、大きい方採用
#
# 3 1 4 1 5 9
# 1 1 3 4 5 9
# 偶数のときは、中央値も2パターン取って大きいのを採用
#
# 5 5 1
# 5 1 5

N=int(input())
A=[0] * N
for i in range(N):
  A[i] = int(input())
  
if N == 2:
  print(abs(A[0] - A[1]))
  exit(0)
  
A=sorted(A)
minA = A[0]
maxA = A[-1]

mid = 0

from collections import deque

def calc(A,first,flip):
  q = deque(A)
  ans = 0
  cur = first
  while q:
    if flip:
      a = q.popleft()
    else:
      a = q.pop()
    ans += abs(a - cur)
    cur = a
    flip^=True
  return ans

if N%2:
  # 奇数のとき
  mid = A.pop(N//2)
  ans1 = calc(A,mid,True)
  ans2 = calc(A,mid,False)
  print(max(ans1,ans2))
  
else:
  # 偶数のとき
  A2 = A.copy()
  mid1 = A.pop(N//2-1)
  ans1_1 = calc(A,mid1,True)
  ans1_2 = calc(A,mid1,False)
  
  mid2 = A2.pop(N//2)
  ans2_1 = calc(A2,mid2,True)
  ans2_2 = calc(A2,mid2,False)
  
  print(max(ans1_1,ans1_2,ans2_1,ans2_2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def func(A):
    N = len(A)
    tmp = N // 2
    T = [0 for _ in range(N)]
    for i in range(0, Math.round_up(N, 2)):
        T[tmp] = A[i]
        if i % 2 == 0:
            tmp -= (i + 1) * 2
        else:
            tmp += (i + 1) * 2
    tmp = N // 2 - 1
    for i in range(0, N // 2):
        T[tmp] = A[N - i - 1]
        if i % 2 == 0:
            tmp += (i + 1) * 2
        else:
            tmp -= (i + 1) * 2
    res = 0
    for i in range(N - 1):
        res += abs(T[i + 1] - T[i])
    return res


def solve():
    N = Scanner.int()
    A = [0 for _ in range(N)]
    for i in range(N):
        A[i] = Scanner.int()
    A.sort()
    ans = func(A)
    A.sort(reverse=True)
    ans = max(ans, func(A))
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque
from math import ceil

n = int(readline())
a = sorted([int(readline()) for i in range(n)])
c = deque(a[:ceil(n / 2)])
d = deque(a[ceil(n / 2):])
b = deque(a[n // 2:])
a = deque(a[:n // 2])
check_1 = deque([a.popleft()])
check_2 = deque([d.pop()])
for i in range(n // 2):
    if i % 2 == 0:
        check_1.appendleft(b.pop())
        check_2.appendleft(c.popleft())
        if len(b) == 0:
            if len(a) != 0:
                check_1.append(a.popleft())
                check_2.append(d.pop())
            break
        check_1.append(b.pop())
        check_2.append(c.popleft())
    else:
        check_1.appendleft(a.popleft())
        check_2.appendleft(d.pop())
        if len(a) == 0:
            if len(b) != 0:
                check_1.append(b.pop())
                check_2.append(c.popleft())
            break
        check_1.append(a.popleft())
        check_2.append(d.pop())
cnt_1 = 0
cnt_2 = 0
for i in range(1, n):
    cnt_1 += abs(check_1[i - 1] - check_1[i])
    cnt_2 += abs(check_2[i - 1] - check_2[i])
print(max(cnt_1, cnt_2))

Submission status: Accepted

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

if n % 2 == 0:
    a_l = a[: n//2]
    a_s = a[n//2:]
    print((2 * sum(a_l) - min(a_l)) - (2 * sum(a_s) - max(a_s)))

else:
    x = 2 * sum(a[:(n-1)//2-1]) + sum(a[(n-1)//2-1:(n-1)//2+1]) - 2 * sum(a[(n-1)//2+1:])
    y = 2 * sum(a[:(n-1)//2]) - sum(a[(n-1)//2:(n-1)//2+2]) - 2 * sum(a[(n-1)//2+2:])
    print(max(x, y))

Submission status: Accepted

Solution code:
N  = int (input())
As = [int(input()) for _ in range(N)]
# print(As)
As.sort()
if N == 1:
    print(0)

#小さい方から配置

elif N == 2:
    print(abs(As[0] - As[1]))
else:
    bottom_ind = 1
    upper_ind = N - 1

    l = r = As[0]

    MA = 1
    MI = 0
    mode = MA

    ans1 = 0
    while True:
        if mode == MA: #上から取る
            next1 = As[upper_ind]
            next2 = As[upper_ind -1]
            ans1 += max(abs(next1 - l ) + abs(next2 - r ),abs(next2 - r ) + abs(next1 - l ))
            r =  next1
            l = next2
            m = upper_ind  - 2
            upper_ind -= 2
            mode = MI

        else:
            next1 = As[bottom_ind]
            next2 = As[bottom_ind + 1]
            ans1 += max(abs(next1 - l) + abs(next2 - r), abs(next2 - r) + abs(next1 - l))
            m = bottom_ind + 2
            bottom_ind+= 2
            r = next1
            l = next2
            mode = MA #下から取る
        if bottom_ind >= upper_ind:
            break
    if N % 2 == 0:
        # m = As[N//2]
        m = As[m]
        ans1 += max( abs(m - l) ,abs(m - r))


    #大きい方から配置

    bottom_ind = 0
    upper_ind = N - 2

    l = r = As[N - 1]


    mode = MI

    ans2 = 0
    while True:
        if mode == MA: #上から取る
            next1 = As[upper_ind]
            next2 = As[upper_ind -1]
            ans2 += max(abs(next1 - l ) + abs(next2 - r ),abs(next2 - r ) + abs(next1 - l ))
            r =  next1
            l = next2
            m = upper_ind  - 2
            upper_ind -= 2
            mode = MI

        else:
            next1 = As[bottom_ind]
            next2 = As[bottom_ind + 1]
            ans2 += max(abs(next1 - l) + abs(next2 - r), abs(next2 - r) + abs(next1 - l))
            m = bottom_ind + 2
            bottom_ind+= 2
            r = next1
            l = next2
            mode = MA #下から取る
        if bottom_ind >= upper_ind:
            break
    if N % 2 == 0:
        # m = As[N//2]
        m = As[m]
        ans2 += max( abs(m - l) ,abs(m - r))





    print(max(ans1,ans2))

Submission status: Accepted

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


if N % 2 == 1:
    L = sorted(L, reverse=True)
    minority = N//2
    majority = N - minority
    A = sum(L[:minority])*2 - sum(L[minority:])*2+sum(L[minority:minority+2])
    B = sum(L[:majority])*2 - sum(L[majority:])*2 - sum(L[majority-2:majority])
    ans = max(A, B)
else:
    L = sorted(L)
    C = sum(L[:N//2])*2 - sum(L[N//2:])*2 + L[N//2]-L[N//2-1]
    D = -C
    ans = max(C, D)
    pass
print(ans)

Submission status: Accepted

Solution code:
# ソートして左右からとっていくが、可能ならば同じ数字が連続しないようにする
# めんどいわ なーにが「可能ならば」じゃ
# 左右どちらを先にとるかでいいんじゃないの
# -> だめでした
# 理屈はわからんが、最後のやつを最初にもっていくやつが浮かんだがなんだこれ
n = int(input())
arr = []
for _ in range(n):
    arr.append(int(input()))
arr = sorted(arr)


def f(arr):
    ans = []
    c, l, r = 0, 0, n - 1
    while c < n:
        if c % 2 == 0:
            ans.append(arr[l])
            l += 1
        else:
            ans.append(arr[r])
            r -= 1
        c += 1
    ans = [ans[-1]] + ans[:-1]
    result, tmp = 0, ans[0]
    for i in range(1, n):
        result += abs(tmp - ans[i])
        tmp = ans[i]
    return result


a, b = f(arr), f(list(reversed(arr)))
print(max(a, b))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
d = deque(A)

#print(d)

# ans1[0] < ans1[1] > ans1[2] という大小関係になる配列を作成する
ans1 = []
for i in range(N):
    x = d.pop() if i % 2 == 0 else d.popleft()
    ans1.append(x)
x = ans1.pop()
ans1 = [x] + ans1

# ans2[0] > ans2[1] < ans2[2] という大小関係になる配列を作成する
ans2 = []
d = deque(A)
for i in range(N):
    x = d.popleft() if i % 2 == 0 else d.pop()
    ans2.append(x)
x = ans2.pop()
ans2 = [x] + ans2


def amount(array):
    ret = 0
    for i in range(N-1):
        ret += abs(array[i+1]-array[i])
    return ret

#print(ans)
print(max(amount(ans1), amount(ans2)))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
d = deque(A)

#print(d)

ans1 = []

for i in range(N):
    x = d.pop() if i % 2 == 0 else d.popleft()
    ans1.append(x)
x = ans1.pop()
ans1 = [x] + ans1

ans2 = []
d = deque(A)
for i in range(N):
    x = d.popleft() if i % 2 == 0 else d.pop()
    ans2.append(x)
x = ans2.pop()
ans2 = [x] + ans2


def amount(array):
    ret = 0
    for i in range(N-1):
        ret += abs(array[i+1]-array[i])
    return ret

#print(ans)
print(max(amount(ans1), amount(ans2)))

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N = int(input())
    A = deque(sorted((int(input()) for i in range(N))))
    dq = deque()
    dq.append(A.popleft())
    ans = 0
    for _ in range(N-1):
        a_first = A[0]
        a_last = A[-1]
        dq_first = dq[0]
        dq_last = dq[-1]

        ff = abs(a_first-dq_first)
        fl = abs(a_first-dq_last)
        lf = abs(a_last-dq_first)
        ll = abs(a_last-dq_last)

        comp_list = [ff, fl, lf, ll]
        max_idx = comp_list.index(max(comp_list))
        if max_idx == 0:
            ans += ff
            dq.appendleft(A.popleft())
        elif max_idx == 1:
            ans += fl
            dq.append(A.popleft())
        elif max_idx == 2:
            ans += lf
            dq.appendleft(A.pop())
        else:
            ans += ll
            dq.append(A.pop())

    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N = int(input())
    A = deque(sorted((int(input()) for i in range(N))))
    dq = deque()
    dq.append(A.popleft())
    for _ in range(N-1):
        a_first = A[0]
        a_last = A[-1]
        dq_first = dq[0]
        dq_last = dq[-1]

        ff = abs(a_first-dq_first)
        fl = abs(a_first-dq_last)
        lf = abs(a_last-dq_first)
        ll = abs(a_last-dq_last)

        comp_list = [ff, fl, lf, ll]
        max_idx = comp_list.index(max(comp_list))
        if max_idx == 0:
            dq.appendleft(A.popleft())
        elif max_idx == 1:
            dq.append(A.popleft())
        elif max_idx == 2:
            dq.appendleft(A.pop())
        else:
            dq.append(A.pop())

    abs_sum = sum([abs(dq[i] - dq[i-1]) for i in range(1, N)])
    print(abs_sum)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = []
for i in range(N):
    A.append(int(input()))

A.sort()


if N % 2 != 0:
    ans1 = 0
    tmp = [-1,-1] + [2]*((N-1)//2) + [-2]*((N-2)//2)
    for i,j in zip(sorted(tmp),A):
        ans1 += (i*j)
    
    ans2 = 0
    tmp = [1,1] + [2]*((N-2)//2) + [-2]*((N-1)//2)
    for i,j in zip(sorted(tmp),A):
        ans2 += (i*j)
    print(max(ans1,ans2))
else:
    ans = 0
    tmp = [-1,1] + [2]*((N-2)//2) + [-2]*((N-2)//2)
    for i,j in zip(sorted(tmp),A):
        ans += (i*j)
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = IR(n)
    a.sort()
    def f(a):
        q = deque(a)
        p = q.popleft()
        ans = deque([p])
        for i in range(n-1):
            if i % 4 in [2, 3]:
                p = q.popleft()
            else:
                p = q.pop()
            if i & 1:
                ans.appendleft(p)
            else:
                ans.append(p)
        num = 0
        for i in range(n - 1):
            num += abs(ans[i + 1] - ans[i])
        return num
    print(max(f(a), f(a[::-1])))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
    A.sort()
    if N % 2 == 0:
        s, l = A[:N//2], A[N//2:]
        ans = 2*(sum(l) - sum(s))
        ans += s[-1] - l[0]
        print(ans)
        return

    sep1 = (N + 1)//2
    s1, l1 = A[:sep1], A[sep1:]
    # print(s1, l1)
    ans1 = 2*(sum(l1) - sum(s1))
    ans1 += s1[-1] + s1[-2]

    sep2 = sep1 - 1
    s2, l2 = A[:sep2], A[sep2:]
    # print(s2, l2)
    ans2 = 2*(sum(l2) - sum(s2))
    ans2 -= l2[0] + l2[1]

    print(max(ans1, ans2))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil
from itertools import permutations


def main():
    length = int(input())
    numbers = [int(input()) for _ in range(length)]
    numbers.sort()
    number_pair = []
    for i in range(ceil(length / 2) - 1):
        number_pair.append([numbers[i], numbers[-i - 1]])
    number_pair.sort(key=lambda x: x[1])
    side = [numbers[length // 2]]
    if length % 2 == 0:
        side.append(numbers[length // 2 - 1])
    else:
        side.append(-1)
    answer = 0
    if 2 < length:
        for left_side, right_side in permutations(side):
            large_first = 0
            small_first = 0
            for i in range(len(number_pair)):
                if i == 0 and left_side != -1:
                    large_first += abs(left_side - number_pair[i][1])
                    small_first += abs(left_side - number_pair[i][0])
                if i == len(number_pair) - 1 and right_side != -1:
                    large_first += abs(right_side - number_pair[i][0])
                    small_first += abs(right_side - number_pair[i][1])
                if 0 < i:
                    large_first += abs(number_pair[i][1] - number_pair[i - 1][0])
                    small_first += abs(number_pair[i][0] - number_pair[i - 1][1])
                large_first += abs(number_pair[i][0] - number_pair[i][1])
                small_first += abs(number_pair[i][0] - number_pair[i][1])
            answer = max(answer, large_first, small_first)
    else:
        answer = abs(numbers[0] - numbers[1])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
if n % 2 == 0:
    plus = a[:n//2]
    minus = a[n//2:]
    ans = (2*sum(plus)-plus[-1]) - (2*sum(minus)-minus[0])
else:
    ans1 = 0
    plus = a[:n//2]
    minus = a[n//2:]
    ans1 = (2*sum(plus)) - (2*sum(minus)-minus[0]-minus[1])

    ans2 = 0
    plus = a[:(n+1)//2]
    minus = a[(n+1)//2:]
    minus.sort()
    ans2 = (2*sum(plus)-plus[-1]-plus[-2]) - (2*sum(minus))

    ans = max(ans1, ans2)

print(ans)

Submission status: Accepted

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

l = A.pop()
r = A.pop(0)
ans = abs(l-r)
while A:
	tmp = [abs(l-A[0]),abs(l-A[-1]),abs(r-A[0]),abs(r-A[-1])]
	cond = tmp.index(max(tmp))

	if cond == 0:
		ans += tmp[0]
		l = A.pop(0)
	elif cond == 1:
		ans += tmp[1]
		l = A.pop()
	elif cond == 2:
		ans += tmp[2]
		r = A.pop(0)
	else:
		ans += tmp[3]
		r = A.pop()

print(ans)

Submission status: Accepted

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

A.sort()

if N%2==0:
    k=N//2
    ans=2*sum(A[k:N])-A[k]-(2*sum(A[0:k])-A[k-1])
    print(ans)
else:
    k=N//2
    ans1=2*sum(A[k+1:N])-2*(sum(A[0:k+1]))+A[k]+A[k-1]
    ans2=2*sum(A[k:N])-A[k]-A[k+1]-2*sum(A[0:k])
    print(max(ans1,ans2))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from copy import deepcopy

def main():
  n = int(input())  
  la = sorted([int(input()) for _ in range(n)])
  
  lo = deepcopy(la)
  ind = 0
  def f(la, ind):
    lx = []
    while len(la) > 0:
      lx.append(la.pop(ind))
      ind = -1 if ind == 0 else 0
    ls = ([abs(lx[i] - lx[i-1]) for i in range(len(lx))])
    return sum(ls)-min(ls)
  print(max(f(deepcopy(la), 0), f(deepcopy(la), -1)))

  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque 
n = int(input())
d = deque()
l=[]
for i in range(n):
  a = int(input())
  l.append(a)
l.sort()
l = deque(l)
flag=0
flag1=0
q = l.popleft()
d.append(q)
while l:
  a =abs(d[0]-l[0])
  b = abs(d[0]-l[-1])
  c = abs(d[-1]-l[-1])
  d1 = abs(d[-1]-l[0])
  m = max(a,b,c,d1)
  if a==m:
    f = l.popleft()
    d.appendleft(f)
  elif b==m:
    f = l.pop()
    d.appendleft(f)
  elif c==m:
    f = l.pop()
    d.append(f)
  elif d1==m:
    f = l.popleft()
    d.append(f)
ans = 0
for i in range(n-1):
  ans+=abs(d[i+1]-d[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque

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

    q = deque()
    q.append(a[0])
    l = 1
    r = n-1
    left = True
    high = True
    ans = 0
    while r - l > 0:
        if high:
            if left:
                ans += abs(a[r] - q[0])
                q.appendleft(a[r])
                r -= 1
                left = False
            else:
                ans += abs(a[r] - q[-1])
                q.append(a[r])
                r -= 1
                left = True
                high = False
        else:
            if left:
                ans += abs(a[l] - q[0])
                q.appendleft(a[l])
                l += 1
                left = False
            else:
                ans += abs(a[l] - q[-1])
                q.append(a[l])
                l += 1
                left = True
                high = True
    
    ans += max(abs(a[l] - q[0]), abs(a[l] - q[-1]))
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = [int(input()) for i in range(n)]
A.sort()
ans = 0
for i in range(n//2):
    ans += (A[i+1]-A[i])*2*(i+1)
    ans += (A[n-1-i]-A[n-1-i-1])*2*(i+1)
    # print(A[i+1], A[i], 2*(i+1))
    # print(A[n-1-i], A[n-1-i-1], 2*(i+1))
if n % 2 == 1:
    ans -= min(A[n//2]-A[n//2-1], A[n//2+1]-A[n//2])
else:
    ans -= (A[n//2] - A[n//2-1]) * (2 * (n//2) + 1)
print(ans)

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_array = [0 for i in range(n)]
#p0 <= p1 >= p2...
coef_1 = [0 for i in range(n)]
coef_1[0] = -1
#p0 >= p1 <= p2 ...
coef_2 = [0 for i in range(n)]
coef_2[0] = 1
index = 0
ans = 0
if n % 2 == 1:
    coef_1[-1] = -1
    coef_2[-1] = 1
else:
    coef_1[-1] = 1
    coef_2[-1] = -1
for i in range(1,n-1):
    if i % 2 == 1:
        coef_1[i] = 2
        coef_2[i] = -2
    else:
        coef_1[i] = -2
        coef_2[i] = 2
coef_2.sort()
coef_1.sort()
ans1 = 0
ans2 = 0
for i in range(n):
    ans1 += coef_1[i]*a[i]
    ans2 += coef_2[i]*a[i]
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
A=sorted(A)
b=(N+1)//2
if N%2==0:
  B=A[:b]
  C=A[b:]
  ans=2*(sum(C)-sum(B))-C[0]+B[-1]
  print(ans)
else:
  B=A[:b-1]
  C=A[b-1:]
  ansa=2*(sum(C)-sum(B))-C[0]-C[1]
  B=A[:b]
  C=A[b:]
  ansb=2*(sum(C)-sum(B))+B[-1]+B[-2]
  print(max(ansa,ansb))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
a.sort()
a=deque(a)
ans=0

big=a.pop()
small=a.popleft()
ans+=big-small
#print(ans,a,big,small)
pre_big=big
pre_small=small
checked_a=deque([small,big])
while(len(a)>1):
    big=a.pop()
    small=a.popleft()
    ans+=pre_big-small
    ans+=big-pre_small
#    print(ans,a,big,small,pre_big,pre_small)
    pre_big=big
    pre_small=small

if(len(a)==1):
    last_a=a.pop()
    ans+=max(pre_big-last_a,last_a-pre_small)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
A.sort()
a, b = [0] * N, [0] * N
c, d = A[:(N + 1) // 2], A[(N + 1) // 2:]
a[0] = c[len(c) - 1]
c.pop()
if N % 2:
	if len(c):
		a[len(a) - 1] = c[len(c) - 1]
		c.pop()
else:
	a[len(a) - 1] = d[0]
	d.pop(0)
e, f = A[:N // 2], A[N // 2:]
b[0] = f[0]
f.pop(0)
if N % 2:
	if len(f):
		b[len(b) - 1] = f[0]
		f.pop(0)
else:
	b[len(b) - 1] = e[len(e) - 1]
	e.pop()
i = 1
while i < N - 1:
	if i % 2:
		a[i] = d[len(d) - 1]
		b[i] = e[len(e) - 1]
		d.pop()
		e.pop()
	else:
		a[i] = c[len(c) - 1]
		b[i] = f[len(f) - 1]
		c.pop()
		f.pop()
	i += 1
g = [0, 0]
i = 1
while i < N:
	g[0] += abs(a[i - 1] - a[i])
	g[1] += abs(b[i - 1] - b[i])
	i += 1
print(max(g[0], g[1]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
a.sort()
b = []
c = []
for i in range(n):
  if i%2:
    b.append(a[i//2])
    c.append(a[i//2+(n+1)//2])
  else:
    b.append(a[i//2+n//2])
    c.append(a[i//2])
if n>=3 and n%2:
  b[-1],b[2] = b[2],b[-1]
  c[0],c[-3] = c[-3],c[0]
ansb = 0
ansc = 0
for i in range(n-1):
  ansb += abs(b[i+1]-b[i])
  ansc += abs(c[i+1]-c[i])
print(max(ansb,ansc))

Submission status: Accepted

Solution code:
n = int(input())
A = [int(input()) for _ in range(n)]
A.sort()
if n % 2 == 0:
  # 同じ長さ
  l = n // 2 - 1
  r = n - 1
  total = 0
  for i in range(n - 1):
    total += A[r] - A[l]
    if i % 2 == 0:
      l = (l + 1) % (n // 2)
    else:
      r -= 1
  print(total)
elif A[n // 2] - A[n // 2 - 1] < A[n // 2 + 1] - A[n // 2]:
  # 小さいほうが両端
  l = n // 2
  r = n - 1
  total = 0
  for i in range(n - 1):
    total += A[r] - A[l]
    if i % 2 == 0:
      l = (l + 1) % (n // 2 + 1)
    else:
      r -= 1
  print(total)
else:
  # 大きいほうが両端
  l = 0
  r = n // 2
  total = 0
  for i in range(n - 1):
    total += A[r] - A[l]
    if i % 2 == 0:
      r -= 1
      if r < n // 2:
        r = n - 1
    else:
      l += 1
  print(total)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = [int(input()) for _ in range(N)]
    a.sort()
    
    if N%2 == 0:
        print(2*sum(a[(N//2):])-a[N//2]-2*sum(a[:(N//2)])+a[N//2-1])
    else:
        x = 2*sum(a[(N//2):])-a[N//2]-a[(N//2)+1]-2*sum(a[:(N//2)])
        y = 2*sum(a[(N//2+1):])-2*sum(a[:(N//2+1)])+a[N//2]+a[N//2-1]
        print(max(x,y))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,*A=map(int, open(0).read().split())
A=sorted(A)
i1=0
i2=N-1
cnt=1
l=1
r=N-2
ans=A[i2]-A[i1]
while cnt<N-1:
    cnt+=1
    j1=max((abs(A[i1]-A[l]),l),(abs(A[i1]-A[r]),r))
    j2=max((abs(A[i2]-A[l]),l),(abs(A[i2]-A[r]),r))
    (j,lr),d=max((j1,1),(j2,2))
    ans+=j
    if d==1:
        i1=lr
    else:
        i2=lr
    if lr==l:
        l+=1
    else:
        r-=1
print(ans)

Submission status: Accepted

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

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

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