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 = [int(input()) for i in range(N)]

A_ = sorted(A)
A_r = list(reversed(A_))

l = []
for i, (x, y) in enumerate(zip(A_[:N//2], A_r[:N//2])):
    if i % 2 == 0:
        l.append(x)
        l.insert(0, y)
    else:
        l.append(y)
        l.insert(0, x)

if N % 2 != 0:
    m = A_[N//2]
    if abs(l[0] - m) > abs(l[-1] - m):
        l.insert(0, m)
    else:
        l.append(m)

def g(L):
    for i, j in zip(L[:-1], L[1:]):
        yield abs(i - j)

print(sum(g(l)))

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
A.sort()
me=1
usr=N-2
lenme=A[0]
lenusr=A[N-1]
ans=A[N-1]-A[0]

for i in range(N-2):
    if max([abs(A[me]-lenme),abs(A[me]-lenusr)])>=max([abs(A[usr]-lenme),abs(A[usr]-lenusr)]):
        if abs(A[me]-lenme)>=abs(A[me]-lenusr):
            ans+=abs(A[me]-lenme)
            lenme=A[me]
        else:
            ans+=abs(A[me]-lenusr)
            lenusr=A[me]
        me+=1
    else:
        if abs(A[usr]-lenme)>=abs(A[usr]-lenusr):
            ans+=abs(A[usr]-lenme)
            lenme=A[usr]
        else:
            ans+=abs(A[usr]-lenusr)
            lenusr=A[usr]
        usr-=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

A = []
for i in range(n):
    A.append(int(input()))
A.sort()
# print(A)

ans = 0
end = [A[0], A[-1]]
ans += abs(A[-1] - A[0])
A = A[1:-1]
s = 0
L = -1
for _ in range(n - 2):
    # print(ans, A, end)
    sl = [A[s], A[L]]
    # print(sl)

    tmp_l = []
    tmp_l.append(abs(end[0] - sl[0]))
    tmp_l.append(abs(end[1] - sl[0]))
    tmp_l.append(abs(end[0] - sl[1]))
    tmp_l.append(abs(end[1] - sl[1]))

    tmp = max(tmp_l)
    index = tmp_l.index(tmp)
    ans += tmp

    # print(index, tmp_l[index])
    if index % 2 == 0:
        end[0] = sl[index == 2]

    else:
        end[1] = sl[index == 3]

    if index < 2:
        s += 1
    else:
        L -= 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

As = sorted(A)
Ar = sorted(A)
Ar.reverse()


cent = (N+1)//2 - 1

ans = [0 for _ in range(N)]
for i in range(cent+1):
    if i == 0:
        ans[cent] = As[0]
    elif i % 2 == 1:
        ans[cent+i] = Ar[i-1]
        ans[cent-i] = Ar[i]
    else:
        ans[cent+i] = As[i-1]
        ans[cent-i] = As[i]

if N % 2 == 0:
    if cent % 2 == 0:
        ans[-1] = Ar[cent]
    else:
        ans[-1] = As[cent]

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

# print(As)
# print(Ar)
# print(ans)
# print(diff)

ans = [0 for _ in range(N)]
for i in range(cent+1):
    if i == 0:
        ans[cent] = Ar[0]
    elif i % 2 == 1:
        ans[cent+i] = As[i-1]
        ans[cent-i] = As[i]
    else:
        ans[cent+i] = Ar[i-1]
        ans[cent-i] = Ar[i]

if N % 2 == 0:
    if cent % 2 == 0:
        ans[-1] = As[cent]
    else:
        ans[-1] = Ar[cent]

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

# print(ans)
# print(diff2)

print(max([diff,diff2]))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
a.sort()
a.reverse()
sum=0
if n%2==1:
    sum1=0
    sum2=0
    for j in range(n):
        if j+1<=n//2:
            sum1+=a[j]*2
        elif j+1<=n//2+2:
            sum1-=a[j]
        else:
            sum1-=a[j]*2
    a.reverse()
    for j in range(n):
        if j+1<=n//2:
            sum2-=a[j]*2
        elif j+1<=n//2+2:
            sum2+=a[j]
        else:
            sum2+=a[j]*2
    sum=max(sum1,sum2)
else:
    for j in range(n):
        if j+1<=n//2-1:
            sum+=a[j]*2
        elif j+1==n//2:
            sum+=a[j]
        elif j+1==n//2+1:
            sum-=a[j]
        else:
            sum-=a[j]*2
print(sum)

Submission status: Accepted

Solution code:
def calc_ans(max_list):
    ans = 0
    for i in range(n - 1):
        ans += abs(max_list[i+1] - max_list[i])
    return ans

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

a.sort()
if n % 2 == 0:
    max_list = []
    mean = n // 2
    list1 = a[mean:]
    list2 = a[:mean]
    for i in range(mean):
        max_list.append(list1[i])
        max_list.append(list2[i])
    ans = calc_ans(max_list)
else:
    max_list = []
    mean = n // 2
    list1 = a[mean:]
    list2 = a[:mean]
    list1[1], list1[-1] = list1[-1], list1[1]
    for i in range(mean):
        max_list.append(list1[i])
        max_list.append(list2[i])
    max_list.append(list1[-1])
    ans = calc_ans(max_list)

    max_list = []
    mean = n // 2 + 1
    list1 = a[:mean]
    list2 = a[mean:]
    list1[0], list1[-2] = list1[-2], list1[0]
    for i in range(mean - 1):
        max_list.append(list1[i])
        max_list.append(list2[i])
    max_list.append(list1[-1])
    ans = max(ans, calc_ans(max_list))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted([int(input()) for _ in range(n)])
if n % 2:
    s = a[:n//2]
    t = a[n//2:]
    ans1 = 2*(sum(t)-sum(s))-t[0]-t[1]
    p = a[:n//2+1]
    q = a[n//2+1:]
    ans2 = 2*(sum(q)-sum(p))+p[-1]+p[-2]
    print(max(ans1, ans2))
else:
    s = a[:n//2]
    t = a[n//2:]
    ans = 2*(sum(t)-sum(s))-t[0]+s[-1]
    print(ans)

Submission status: Accepted

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

B=sorted(A)
#print(B[N-1]-B[0] + B[N-1]-B[0])
hN=int(N/2)
cnt=0
C=[]
if N ==2:
    print(B[1]-B[0])
    exit()

if N %2 == 0:
    C.append(B[hN])
    for i in range(hN-1):
        C.append(B[N-1-i])
        C.append(B[i])
    C.append(B[hN-1])
else:
    C.append(B[hN])
    for i in range(hN):
        C.append(B[N-1-i])
        C.append(B[i])

#print(C)

for i in range(1,N):
    cnt+=abs(C[i]-C[i-1])

C=[]
cnt2=0
if N %2 == 0:
    C.append(B[hN])
    for i in range(hN-1):
        C.append(B[i])
        C.append(B[N-1-i])
    C.append(B[hN-1])
else:
    C.append(B[hN])
    for i in range(hN):
        C.append(B[i])
        C.append(B[N-1-i])

#print(C)
for i in range(1,N):
    cnt2+=abs(C[i]-C[i-1])

print(max(cnt,cnt2))

Submission status: Accepted

Solution code:

N = int(input())
Alist=[]
# Blist=[]
for i in range(0,N):
    Alist.append(int(input()))

Alist.sort()
# print(Alist)

back=N-1

numA=Alist[0]
numB=Alist[back]
ans = abs(numB-numA)
back-=1
# print(ans)

for i in range(1,int(N/2)):
    if i%2 == 0:
        ans+=abs(numA-Alist[i])
        numA=Alist[i]
        ans+=abs(numB-Alist[back])
        numB=Alist[back]
        # print(ans)
    else:
        ans+=abs(numB-Alist[i])
        numB=Alist[i]
        ans+=abs(numA-Alist[back])
        numA=Alist[back]
    back-=1
    # print(ans)

# print("l-")

if N%2 == 1:
    k=int(N/2)
    # print(k)
    if abs(numA-Alist[k]) > abs(numB-Alist[k]):
        ans+=abs(numA-Alist[k])
        numA=Alist[k]
    else:
        ans+=abs(numB-Alist[k])
        numB=Alist[k]
    # print(ans)

# print("a-")
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
b = []
for I in range(n-1):
 b.append(a[I+1]-a[I])
s = 0
if n%2 == 0:
 for j in range(int(n/2)-1):
  s += 2*(j+1)*(b[j] + b[n-j-2])
 s += b[int(n/2) - 1]*(2*int(n/2)-1)
if n%2 == 1:
 for j in range(int((n-1)/2)):
  s += 2*(j+1)*(b[j] + b[n-j-2])
 s -= min(b[int((n-1)/2)-1],b[int((n-1)/2)])

print(s)

Submission status: Accepted

Solution code:
# encoding: utf-8
import math, sys

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

A_up = sorted(A)
A_down = list(A_up[::-1])

# magic-hand-like order
# 1 2 3
# |X X  4 <- this node is taken last
# 7 6 5

ans = 0
for i in range(N // 2):
    if i == 0:
        ans += (A_down[0] - A_up[0])
    else:
        ans += (A_down[i - 1] - A_up[i])
        ans += (A_down[i] - A_up[i - 1])

if N % 2:
    ans += max((A_down[N // 2 - 1] - A_down[N // 2], A_up[N // 2] - A_up[N // 2 - 1]))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
s1=0
s2=0
for i in range(n):
    t=int(input())
    a.append(t)
a.sort()
if n==2:
    print(a[1]-a[0])
elif n%2==0:
    m=(n-2)//2
    
    for i in range(m):
        s1=s1-2*a[i]
    s1=s1-a[m]
    s1=s1+a[m+1]
    for i in range(m+2,n):
        s1=s1+2*a[i]
    print(max(s1,s2))
elif n==3:
    print(max((a[2]-a[0]+a[1]-a[0]),(a[2]-a[1]+a[2]-a[0])))
elif n%2==1:
    m=(n-2)//2
    
    for i in range(m):
        s1=s1-a[i]*2
    s1=s1-a[m]
    s1=s1-a[m+1]
    for i in range(m+2,n):
        s1=s1+2*a[i]
    
    for i in range(m+1):
        s2=s2-a[i]*2
    s2=s2+a[m+1]
    s2=s2+a[m+2]
    for i in range(m+3,n):
        s2=s2+2*a[i]
    
    print(max(s1,s2))

Submission status: Accepted

Solution code:
from sys import stdin


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

    i = 0
    j = len(a) - 1
    flg = False
    left = right = 0
    ans = 0
    while i <= j:
        if not flg:
            if (a[-1] * 2 - a[0] - a[1]) > (a[-1] + a[-2] - a[0] * 2):
                left = right = a[-1]
                j -= 1
            else:
                left = right = a[0]
                i += 1
            flg = True
        else:
            best = (0, 0)
            for k, v in enumerate([left - a[i], left - a[j], right - a[i], right - a[j]]):
                if best[1] < abs(v):
                    best = (k, abs(v))
            ans += best[1]
            if best[0] == 0:
                left = a[i]
                i += 1
            elif best[0] == 1:
                left = a[j]
                j -= 1
            elif best[0] == 2:
                right = a[i]
                i += 1
            elif best[0] == 3:
                right = a[j]
                j -= 1

    print(ans)


def next_str() -> str:
    result = ""
    while True:
        tmp = stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import copy
from collections import deque

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

aN_sorted = sorted(aN)
aN_sorted = deque(aN_sorted)
aN2 = [0] * N
for i in range(N):
    if i % 2 == 0:
        aN2[i] = aN_sorted.popleft()
    else:
        aN2[i] = aN_sorted.pop()
aN_sorted2 = sorted(aN, reverse=True)
aN_sorted2 = deque(aN_sorted2)
aN3 = [0] * N
for i in range(N):
    if i % 2 == 0:
        aN3[i] = aN_sorted2.popleft()
    else:
        aN3[i] = aN_sorted2.pop()

ans = 0
for i in range(1,N):
    if i == N-1:
        ans += max(abs(aN2[i-1] - aN2[i]), abs(aN2[i] - aN2[0]))
    else:
        ans += abs(aN2[i-1] - aN2[i])
ans2 = 0
for i in range(1,N):
    if i == N-1:
        ans2 += max(abs(aN3[i-1] - aN3[i]), abs(aN3[i] - aN3[0]))
    else:
        ans2 += abs(aN3[i-1] - aN3[i])

print(max(ans, ans2))

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 = sorted(a)
sum = 0

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

    sum2 = 0
    for i in range(int(n/2), n):
        sum2 += a[i] * 2
    sum2 -= a[int(n / 2)]
    sum2 -= a[int(n / 2)+1]
    for i in range(int(n / 2)):
        sum2 -= a[i]*2
    print(max(sum1, sum2))
else:
    sum += a[int(n / 2)]
    for i in range(int(n / 2)+1, n):
        sum += a[i] * 2
    sum -= a[int(n / 2) - 1]
    for i in range(int(n / 2) - 1):
        sum -= a[i] * 2
    print(sum)

Submission status: Accepted

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

if N % 2 == 1:
    mid = A[N // 2]
#     print(mid)
    A = sorted([abs(a-mid) for a in A])
#     print(A)
    print(sum(A[:2]) + 2 * sum(A[2:]))

else:
    mid1 = A[N // 2 - 1]
    mid2 = A[N // 2]
    A_ori = [a for a in A]
    
    # 1
    A = [abs(a-mid1) for a in A_ori]
    one = A.pop(N // 2)
    two = A.pop(N // 2 - 1)
    cand = one + two + 2 * sum(A)
    
    # 2
    A = [abs(a-mid2) for a in A_ori]
    one = A.pop(N // 2)
    two = A.pop(N // 2 - 1)
    cand2 = one + two + 2 * sum(A)

#     print(cand, cand2)
    print(max(cand, cand2))

Submission status: Accepted

Solution code:
n = int(input())

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

a = sorted(a)

ans = 0

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

else:
    r = a[n//2]
    if r - a[n//2-1] < a[n//2+1] - r:
        for i in range(n//2):
            q = a[-i-1]
            p = a[i]
            ans += abs(q-r) + abs(p-q)
            r = p
    else:
        for i in range(n//2):
            q = a[i]
            p = a[-i-1]
            ans += abs(q-r) + abs(p-q)
            r = p

print(ans)

Submission status: Accepted

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

def solve2(a):
  i = 1
  j = n-1
  s = 0
  x = y = a[0]
  r = True
  while i<j:
    if r:
      s += abs(a[j] - x) + abs(a[j-1] - y)
      x = a[j]
      y = a[j-1]
      j -= 2
    else:
      s += abs(a[i] - x) + abs(a[i+1] - y)
      x = a[i]
      y = a[i+1]
      i += 2
    r = not r
  if i == j:
    s += max(abs(a[i] - x), abs(a[i]-y))
  return s

print(max(solve2(sorted(a)), solve2(sorted(a, reverse=True))))

Submission status: Accepted

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort()# ソート
hashi = [a[0], a[-1]]
total = abs(a[0] - a[-1])

s = 1
e = n - 2
if n == 2:
    print(total)
    exit()
while True:
    max_diff = 0
    point = "s"
    h = "s"
    if max_diff < abs(hashi[0] - a[s]):
        max_diff = abs(hashi[0] - a[s])
        point = "s"
        h = "s"
    if max_diff < abs(hashi[0] - a[e]):
        max_diff = abs(hashi[0] - a[e])
        point = "e"
        h = "s"
    if max_diff < abs(hashi[1] - a[s]):
        max_diff = abs(hashi[1] - a[s])
        point = "s"
        h = "e"
    if max_diff < abs(hashi[1] - a[e]):
        max_diff = abs(hashi[1] - a[e])
        point = "e"
        h = "e"
    total += max_diff
    if h == "s":
        if point == "s":
            hashi[0] = a[s]
        if point == "e":
            hashi[0] = a[e]
    if h == "e":
        if point == "s":
            hashi[1] = a[s]
        if point == "e":
            hashi[1] = a[e]
    if point == "s":
        s += 1
    if point == "e":
        e -= 1
    if s - 1 == e:
        break
print(total)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):A.append(int(input()))
A=sorted(A)
B=[0]*N
if N%2==0:
    for i in range(N):
        if i==N//2-1:
            B[0]=A[i]
        elif i<N//2-1:
            B[i*2+2]=A[i]
        else:
            B[-(i-N//2)*2-1]=A[i]
else:
    for i in range(N):
        if i==N//2:
            B[0]=A[i]
        elif i<N//2:
            B[i*2+2]=A[i]
        else:
            B[-(i-N//2)*2]=A[i]
r=0
for i in range(1,N):
    r += abs(B[i-1]-B[i])
A=A[::-1]
B=[0]*N
if N%2==0:
    for i in range(N):
        if i==N//2-1:
            B[0]=A[i]
        elif i<N//2-1:
            B[i*2+2]=A[i]
        else:
            B[-(i-N//2)*2-1]=A[i]
else:
    for i in range(N):
        if i==N//2:
            B[0]=A[i]
        elif i<N//2:
            B[i*2+2]=A[i]
        else:
            B[-(i-N//2)*2]=A[i]
s=0
for i in range(1,N):
    s += abs(B[i-1]-B[i])
print(max(r,s))

Submission status: Accepted

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

a = sorted(a)

sum_1 = 0
sum_2 = 0
if len(a) % 2 == 1:
    for i in range(0, len(a)//2):
        sum_1 += a[-i-1] - a[i]
        sum_2 += a[-i-1] - a[i]
    for i in range(1, len(a)//2):
        sum_1 += a[-i] - a[i]
    for i in range(0, len(a)//2-1):
        sum_2 += a[-i-2] - a[i]
    sum_1 += a[len(a)//2]-a[0]
    sum_2 += a[-1]-a[len(a)//2]
    print(max(sum_1, sum_2))

else:
    for i in range(0, len(a)//2-1):
        sum_1 += a[-i-1] - a[i]
        sum_2 += a[-i-1] - a[i]
    for i in range(1, len(a)//2):
        sum_1 += a[-i] - a[i]
    for i in range(0, len(a)//2-1):
        sum_2 += a[-i-2] - a[i]
    sum_1 += a[-len(a)//2] - a[0]
    sum_2 += a[-1] - a[len(a)//2-1]
    print(max(sum_1, sum_2))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
min = 1
max = N-1
ans = [0 for _ in range(2*N+10)]
ans[len(ans)//2] = A[0]
l = len(ans) // 2
r = l
for i in range(1, N):
    left = False
    minS = False
    maxx = -1
    if abs(ans[l]-A[min]) > maxx:
        left = True
        minS = True
        maxx = abs(ans[l]-A[min])
    if abs(ans[l]-A[max]) > maxx:
        left = True
        minS = False
        maxx = abs(ans[l]-A[max])
    if abs(ans[r]-A[min]) > maxx:
        left = False
        minS = True
        maxx = abs(ans[r]-A[min])
    if abs(ans[r]-A[max]) > maxx:
        left = False
        minS = False
        maxx = abs(ans[r]-A[max])

    if left and minS:
        l -= 1
        ans[l] = A[min]
        min += 1
    elif left and not minS:
        l -= 1
        ans[l] = A[max]
        max -= 1
    elif not left and minS:
        r += 1
        ans[r] = A[min]
        min += 1
    else:
        r += 1
        ans[r] = A[max]
        max -= 1
an = 0
for i in range(l+1, r+1):
    an += abs(ans[i]-ans[i-1])
#print(ans)
print(an)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
a.sort(reverse=True)
ans=0
ans1=0
ans2=0
if n%2==0:
    for i in range(n//2):
        if i==n//2-1:
            ans+=a[i]
        else:
            ans+=2*a[i]
    for i in range(n-1,n//2-1,-1):
        if i==n//2:
            ans-=a[i]
        else:
            ans-=2*a[i]
else:
    for i in range((n+1)//2):
        if (i==(n-3)//2)|(i==(n-1)//2):
            ans1+=a[i]
        else:
            ans1+=2*a[i]
    for i in range((n+1)//2,n):
        ans1-=2*a[i]
    for i in range((n-1)//2):
        ans2+= 2 * a[i]
    for i in range((n-1)//2,n):
        if (i == (n-1)//2) | (i ==(n+1)//2):
            ans2-=a[i]
        else:
            ans2-=2 * a[i]
    ans=max(ans1,ans2)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = []
L2 = []
for i in range(N) :
    l = int(input())
    L.append(l)
    L2.append(l)
L = sorted(L)
L2 = sorted(L2)
ANS = []
for i in range(2) :
    ans = 0
    turn = i
    flag = 0
    B = []
    if i == 0 :
        while len(L) != 0 :
            if len(L) == 1 :
                r = L[0]
                L.pop(0)
            else :
                if turn == 0 :
                    p = L[-1]
                    if flag != 0 :
                        ans += abs(p-q)
                    else :
                        B.append(p)
                        flag = 1
                    L.pop(-1)
                    turn = 1
                else :
                    q = L[0]
                    if flag != 0 :
                        ans += abs(p-q)
                    else :
                        B.append(q)
                        flag = 1
                    L.pop(0)
                    turn = 0

        ans += abs(r-B[0])
        ANS.append(ans)
        
    else :
        while len(L2) != 0 :
            if len(L2) == 1 :
                r = L2[0]
                L2.pop(0)
            else :
                if turn == 0 :
                    p = L2[-1]
                    if flag != 0 :
                        ans += abs(p-q)
                    else :
                        B.append(p)
                        flag = 1
                    L2.pop(-1)
                    turn = 1
                else :
                    q = L2[0]
                    if flag != 0 :
                        ans += abs(p-q)
                    else :
                        B.append(q)
                        flag = 1
                    L2.pop(0)
                    turn = 0

        ans += abs(r-B[0])
        ANS.append(ans)
        
        
print(max(ANS))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for x in range(N)]
A.sort()
l = len(A)//2
if  len(A)%2 == 1:
    one = 2*sum(A[l+1::])-2*sum(A[:l+1:])+A[l-1]+A[l]
    two = 2*sum(A[l::])-2*sum(A[:l:])-A[l]-A[l+1]
    print(max(one,two))
else:
    print(2*sum(A[l::])-2*sum(A[:l:])-A[l]+A[l-1])

Submission status: Accepted

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

a = sorted(a)
l = len(a)

if n % 2 == 0:
    # 谷max, 山, 谷, ..., 山, 谷, 山min
    tani = sorted(a[:l // 2], reverse=True)
    yama =  a[l // 2 + 1:] + [a[l // 2]]
    ans = 0
    for i in range(l //2):
        ans += yama[i] - tani[i]
    for i in range(l //2 - 1):
        ans += yama[i] - tani[i + 1]
    print(ans)

else:
    # 谷max, 山, 谷, ..., 山, 谷max
    tani = sorted(a[:l // 2 + 1], reverse=True)
    tani = tani[1:] + [tani[0]]
    yama = a[l // 2 + 1:]
    t = 0
    for i in range(l // 2):
        t += yama[i] - tani[i]
    for i in range(l // 2):
        t += yama[i] - tani[i + 1]
    ans = t

    # 山min, 谷, 山, ..., 谷, 山min
    tani = sorted(a[:l // 2], reverse=True)
    yama = a[l // 2:]
    yama = yama[1:] + [yama[0]]
    t = 0
    for i in range(l // 2):
        t += yama[i] - tani[i]
    for i in range(l // 2):
        t += yama[i + 1] - tani[i]

    ans = max(ans, t)
    print(ans)

Submission status: Accepted

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

    if n % 2 == 0:
        print(even_pattern(a))
    else:
        print(max(odd_pattern1(a), odd_pattern2(a)))

def odd_pattern1(a):
    m = len(a) // 2
    s = 0
    s += 2 * sum(a[:m])
    s -= sum(a[m:m+2])
    s -= 2 * sum(a[m+2:])
    return s

def odd_pattern2(a):
    m = len(a) // 2 - 1
    s = 0
    s += 2 * sum(a[:m])
    s += sum(a[m:m+2])
    s -= 2 * sum(a[m+2:])
    return s

def even_pattern(a):
    m = len(a) // 2 - 1
    s = 0
    s += 2 * sum(a[:m])
    s += a[m]
    s -= a[m+1]
    s -= 2 * sum(a[m+2:])
    return s

main()

Submission status: Accepted

Solution code:
N=int(input())
l=list(int(input()) for i in range(N))
l.sort()
m=l[:]
a=b=l.pop(0)
ansA=0
for i in range(0,len(l)):
    if i%4==0:
        ansA+=l[-1]-a
        c=l.pop(-1)
    elif i%4==1:
        ansA+=l[-1]-b
        d=l.pop(-1)
    elif i%4==2:
        ansA+=c-l[0]
        a=l.pop(0)
    else:
        ansA+=d-l[0]
        b=l.pop(0)
c=d=m.pop(-1)
ansB=0
for i in range(0,len(m)):
    if i%4==2:
        ansB+=m[-1]-a
        c=m.pop(-1)
    elif i%4==3:
        ansB+=m[-1]-b
        d=m.pop(-1)
    elif i%4==0:
        ansB+=c-m[0]
        a=m.pop(0)
    else:
        ansB+=d-m[0]
        b=m.pop(0)
print(max([ansA,ansB]))

Submission status: Accepted

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

ans=0
if n%2==1:
  aList.sort()
  smallList1=aList[:(n+1)//2]
  bigList1=aList[(n+1)//2:]
  ans1=sum(bigList1)*2-sum(smallList1)*2+smallList1[-1]+smallList1[-2]

  smallList2=aList[:(n-1)//2]
  bigList2=aList[(n-1)//2:]
  ans2=sum(bigList2)*2-sum(smallList2)*2-bigList2[0]-bigList2[1]
  ans=max(ans1,ans2)
else:
  aList.sort()
  smallList=aList[:n//2]
  bigList=aList[n//2:]
  ans=sum(bigList)*2-sum(smallList)*2+smallList[-1]-bigList[0]
print(ans)

Submission status: Accepted

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

a = sorted(a)
que1 = deque([a[0]])
for i in range(1, n):
    if i%4 == 1:
        que1.appendleft(a[-(2*(i//4)+1)])
    elif i%4 == 2:
        que1.append(a[-(2*(i//4)+2)])
    elif i%4 == 3:
        que1.appendleft(a[2*(i//4)+1])
    else:
        que1.append(a[i//2])

que2 = deque([a[-1]])
for i in range(n-1):
    if i%4 == 0:
        que2.appendleft(a[i//2])
    elif i%4 == 1:
        que2.append(a[2*(i//4)+1])
    elif i%4 == 2:
        que2.appendleft(a[-(i//2+1)])
    else:
        que2.append(a[-(i//2+2)])

sum1 = 0
i = que1.popleft()
while len(que1) > 0:
    j = que1.popleft()
    sum1 += abs(i - j)
    i = j

sum2 = 0
i = que2.popleft()
while len(que2) > 0:
    j = que2.popleft()
    sum2 += abs(i-j)
    i = j
    
print(max(sum1, sum2))

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
A=[int(input()) for i in range(N)]
A=np.array(sorted(A))
ans=0

lenA=len(A)
mid=lenA//2

if lenA%2==0:
    ans+=A[mid]
    ans-=A[mid-1]
    if N>2:
        ans+=2*sum(A[mid+1:])
        ans-=2*sum(A[:mid-1])
else:
    ans+=A[mid]+A[mid+1]
    ans-=2*sum(A[:mid])
    
    tmp=2*sum(A[mid+1:])
    tmp-=A[mid]+A[mid-1]
    if N>3:
        ans+=2*sum(A[mid+2:])
        tmp-=2*sum(A[:mid-1])
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8

N = int(input())
ls = []
for n in range(N):
    ls.append(int(input()))
ls.sort()
rm = []
temp = ls.pop(0)
rm.append(temp)
temp = ls.pop(-1)
rm.append(temp)
ans = rm[-1]-rm[0]
while(1):
    if len(ls)==0:
        break
    mx = 0
    for rm_index in range(2):
        for ls_index in [0,-1]:
            dist = abs(rm[rm_index]-ls[ls_index])
            if dist >= mx:
                mx = dist
                arg_rm = rm_index
                arg_ls = ls_index
    ans += mx
    rm[arg_rm] = ls.pop(arg_ls)
    #print(rm,ls)
print (ans)

Submission status: Accepted

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

if N%2==0:
    l1=a[:N//2]
    l2=a[N//2:N]
    ans=0
    for i in range(len(l1)):
        ans-=l1[i]*2
    ans+=l1[-1]
    for i in range(len(l2)):
        ans+=l2[i]*2
    ans-=l2[0]
else:
    l11=a[:N//2+1]
    l21=a[N//2+1:N]

    ans1=0
    for i in range(len(l11)):
        ans1-=l11[i]*2
    ans1+=l11[-1]+l11[-2]
    for i in range(len(l21)):
        ans1+=l21[i]*2

    l12=a[:N//2]
    l22=a[N//2:N]

    ans2=0
    for i in range(len(l12)):
        ans2-=l12[i]*2

    for i in range(len(l22)):
        ans2+=l22[i]*2
    ans2-=l22[0]+l22[1]
    ans=max(ans1,ans2)
print(ans)

Submission status: Accepted

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

A.sort()
sum = 0
sum2 = 0

if N % 2 == 0:
    A1 = A[:(N//2)]
    A2 = A[(N//2):]
    for i in range(N//2):
        sum += A2[i] - A1[i]
        if i+1 != N//2:
            sum += A2 [i+1] - A1[i]

else:
    A1 = A[:(N//2)]
    A2 = A[(N//2)+1:]
    A3 = A[(N//2)]

    for i in range(N//2):
        sum += A2[i] - A1[i]
        if i+1 != N//2:
            sum += A2 [i+1] - A1[i]
    sum += A3 - A1[N//2 -1]

    sum2 += A2[0] - A3
    for i in range(N // 2):
        sum2 += A2[i] - A1[i]
        if i + 1 != N // 2:
            sum2 += A2[i + 1] - A1[i]

    if sum2 > sum:  sum = sum2

print(sum)

Submission status: Accepted

Solution code:
N = int(input())
arr = [int(input()) for i in range(N)]
arr.sort()
m = N // 2

if N % 2 ==0:
  high = sum(arr[m:])
  low  = sum(arr[:m])
  print((high - low) * 2 - (arr[m] - arr[m-1]))
else:
  center = arr[m]
  high = sum(arr[m+1:])
  low = sum(arr[:m])
  dl = center - arr[m-1]
  dh = arr[m+1] - center
  if dl > dh:
    print((high - low) * 2 - dh)
  else:
    print((high - low) * 2 - dl)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
    n=int(input())
    A.append(n)
A.sort()
if N%2==1:
    ans1=0
    B=A[int(N/2)]
    for j in range(int(N/2)):
        ans1+=abs(B-A[j])
        B=A[j]
        ans1+=abs(B-A[N-1-j])
        B=A[N-1-j]
    ans2=0
    C=A[int(N/2)]
    for k in range(int(N/2)):
        ans2+=abs(C-A[N-1-k])
        C=A[N-1-k]
        ans2+=abs(C-A[k])
        C=A[k]
    print(max(ans1,ans2))
else:
    ans1=0
    B=A[int(N/2)]
    for j in range(int(N/2)-1):
        ans1+=abs(B-A[j])
        B=A[j]
        ans1+=abs(B-A[N-1-j])
        B=A[N-1-j]
    ans1+=abs(B-A[int(N/2)-1])
    ans2=0
    C=A[int(N/2)-1]
    for k in range(int(N/2)-1):
        ans2+=abs(C-A[k])
        C=A[k]
        ans2+=abs(C-A[N-1-k])
        C=A[N-1-k]
    ans2+=abs(C-A[int(N/2)])
    print(max(ans1,ans2))

Submission status: Accepted

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

B = A[:]
A.sort()
B.sort(reverse=True)
A = [A[(n-1)//2]] + [A[0]] + A[1:n//2]

ans = 0
prev = A[0]
for i in range(n):
    if i % 2 == 0:
        ans += abs(prev-A[i//2])
        prev = A[i//2]
    else:
        ans += abs(prev-B[i//2])
        prev = B[i//2]

A = B[:]
A.sort()
B = [B[(n-1)//2]] + [B[0]] + B[1:n//2]

ans2 = 0
prev = B[0]

for i in range(n):
    if i % 2 == 1:
        ans2 += abs(prev-A[i//2])
        prev = A[i//2]
    else:
        ans2 += abs(prev-B[i//2])
        prev = B[i//2]

print(max(ans, ans2))

Submission status: Accepted

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

def do(i):
    if i==0:
        return 0, 1
    else:
        return i+1, i-1
    
score = 0
for i in range(n//2):
    a, b = do(i)
    score += vs[-a-1] + vs[-b-1] - vs[i]*2
if n % 2 == 1:
    v = (vs[(n//2)+1] - vs[n//2]) - (vs[(n//2)] - vs[(n//2)-1])
    if v > 0:
        score += v
print(score)

Submission status: Accepted

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

a.sort()

ans = 0

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

if n%2==1:
    if a[n//2+1]-a[n//2]>a[n//2]-a[n//2-1]:
        ans += a[n//2+1]*2-a[n//2]-a[n//2-1]
    else:
        ans += a[n//2+1]+a[n//2]-a[n//2-1]*2

print(ans)

Submission status: Accepted

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

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

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:
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
a.sort()
if n%2 == 0:
    print(2*(sum(a[n//2:])-sum(a[:n//2]))-(a[n//2]-a[n//2-1]))
else:
    print(2*(sum(a[n//2+1:])-sum(a[:n//2]))-min(a[n//2]-a[n//2-1],a[n//2+1]-a[n//2]))