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

A = sorted(A)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[4]:


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


# In[6]:


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

Submission status: Accepted

Solution code:

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

# def main():

    # N = int(input())

    # for i in range(N):
    #     v = int(input())
    #     h.append(v)
def main():
    N, *h = map(int, read().split())
    h.sort()
    hh = h.copy()

    ans = 0
    t = h.pop(-1)
    t1 = t
    pm = 0
    while 1:
        t2 = h.pop(pm)
        ans += abs(t - t2)
        if len(h) == 0:
            break
        t = t2

        t3 = h.pop(pm)
        ans += abs(t1 - t3)
        if len(h) == 0:
            break
        t1 = t3

        if pm==0:
            pm = -1
        else:
            pm = 0

    ans1 = 0
    h = hh
    t = h.pop(0)
    t1 = t
    pm = -1

    while 1:
        t2 = h.pop(pm)
        ans1 += abs(t - t2)
        if len(h) == 0:
            break
        t = t2

        t3 = h.pop(pm)
        ans1 += abs(t1 - t3)
        if len(h) == 0:
            break
        t1 = t3
        if pm == 0:
            pm = -1
        else:
            pm = 0

    print(max(ans, ans1))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h = []
N = int(input())

for i in range(N):
    v = int(input())
    h.append(v)
h.sort()
hh = h.copy()

ans = 0
t = h.pop(-1)
t1 = t
pm = 0
while 1:
    t2 = h.pop(pm)
    ans += abs(t - t2)
    if len(h) == 0:
        break
    t = t2

    t3 = h.pop(pm)
    ans += abs(t1 - t3)
    if len(h) == 0:
        break
    t1 = t3

    if pm==0:
        pm = -1
    else:
        pm = 0

ans1 = 0
h = hh
t = h.pop(0)
t1 = t
pm = -1

while 1:
    t2 = h.pop(pm)
    ans1 += abs(t - t2)
    if len(h) == 0:
        break
    t = t2

    t3 = h.pop(pm)
    ans1 += abs(t1 - t3)
    if len(h) == 0:
        break
    t1 = t3
    if pm == 0:
        pm = -1
    else:
        pm = 0


print(max(ans, ans1))

Submission status: Accepted

Solution code:
N = int(input())

A = [int(input()) for _ in range(N)]
A.sort()
B = A[::-1]

l1 = []
l2 = []
for i in range((N + int(N % 2 == 0)) // 2):
    l1.append(A[i])
    l1.append(B[i])
    l2.append(B[i])
    l2.append(A[i])

a, b = 0, 0
for i in range(N - int(N % 2 == 1) - 1):
    a += abs(l1[i] - l1[i + 1])
    b += abs(l2[i] - l2[i + 1])

# print(a)
# print(b)
if N % 2 == 0:
    a -= abs(l1[-1] - l1[-2])
    b -= abs(l2[-1] - l2[-2])
    a += max(abs(l1[0] - l1[-1]), abs(l1[-2] - l1[-1]))
    b += max(abs(l2[0] - l2[-1]), abs(l2[-2] - l2[-1]))
else:
    a += max(abs(l1[0] - A[(N - 1) // 2]), abs(l1[-1] - A[(N - 1) // 2]))
    b += max(abs(l2[0] - A[(N - 1) // 2]), abs(l2[-1] - A[(N - 1) // 2]))
res = max(a, b)

# print(l1)
# print(l2)
print(res)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
M = N // 2
A.sort()
ans = 0
if N % 2:
    for i in range(1, M):
        ans += A[i + M + 1] - A[i - 1]
        ans += A[i + M + 1] - A[i]
    ans += A[M + 1] - A[0]
    ans = max(A[M + 1] - A[M] + ans, ans + A[M] - A[M - 1])
else:
    ans += A[M] - A[0]
    for i in range(1, M):
        ans += A[i + M] - A[i - 1]
        ans += A[i + M] - A[i]
print(ans)

Submission status: Accepted

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

A.sort()

if n%2 == 0:
    ans = A[n//2]-A[n//2-1]
    m = A[n//2]-A[n//2-1]
    for i in range(n):
        if i == n//2-1 or i == n//2:
            continue
        else:
            if i <= n//2:
                ans += m-2*A[i]
            else:
                ans += 2*A[i]-m
else:
    m = A[n//2]
    ans1 = m-A[n//2-1]
    for i in range(n):
        if i == n//2-1 or i == n//2:
            continue
        else:
            ans1 += 2*abs(A[i]-m)
    m = A[n//2]
    ans2 = A[n//2+1]-m
    for i in range(n):
        if i == n//2+1 or i == n//2:
            continue
        else:
            ans2 += 2*abs(A[i]-m)
    ans = max(ans1, ans2)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(input()) for _ in range(N)])
if N%2==0:
    B = A[:N//2]
    C = A[N//2:]
    C = C[::-1]
    D1 = []
    D2 = []
    for i in range(N//2-1):
        D1.append(B[i])
        D1.append(C[i])
        D2.append(C[i])
        D2.append(B[i])
    D1.append(B[-1])
    D1.insert(0,C[-1])
    D2.append(C[-1])
    D2.insert(0,B[-1])
    cnt1 = 0
    cnt2 = 0
    for i in range(1,N):
        cnt1 += abs(D1[i]-D1[i-1])
        cnt2 += abs(D2[i]-D2[i-1])
    print(max(cnt1,cnt2))
else:
    B = A[:N//2]
    C = A[N//2+1:]
    C = C[::-1]
    D1 = []
    D2 = []
    for i in range(N//2):
        D1.append(B[i])
        D1.append(C[i])
        D2.append(C[i])
        D2.append(B[i])
    cnt1 = 0
    cnt2 = 0
    for i in range(1,N-1):
        cnt1 += abs(D1[i]-D1[i-1])
        cnt2 += abs(D2[i]-D2[i-1])
    cnt1 += max(A[N//2]-D1[0],D1[-1]-A[N//2])
    cnt2 += max(D2[0]-A[N//2],A[N//2]-D2[-1])
    print(max(cnt1,cnt2))

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    A.sort()
    B = [A[i // 2] if i & 1 == 0 else A[-1 - i // 2] for i in range(N)]
    C = [A[i // 2] if i & 1 == 1 else A[-1 - i // 2] for i in range(N)]

    print(max(f(B), f(C)))

def f(L):
    res = 0
    for i in range(len(L) - 1):
        res += abs(L[i] - L[i - 1])
    return res

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    main(N, A)

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

N = ii()
A = [ii() for i in range(N)]

A.sort()
u1, u2 = [], []
l1, l2 = [], []
for i in range(N):
    if i < N//2:
        l1.append(A[i])
    else:
        u1.append(A[i])

    if i < (N+1)//2:
        l2.append(A[i])
    else:
        u2.append(A[i])

if N%2:
    ans = max(
        (2*sum(u1)-u1[0]-u1[1]) - 2*sum(l1),
        2*sum(u2) - (2*sum(l2)-l2[-1]-l2[-2])
    )
else:
    ans = (2*sum(u1)-u1[0]) - (2*sum(l1)-l1[-1])

print(ans)

Submission status: Accepted

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


def f(A, N):
    l = [0]*N
    a = (N+1)//2

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

    if N%2==1:
        l[-1], l[2] = l[2], l[-1]

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

    return s


print(max(f(A, N), f(list(reversed(A)), N)))

Submission status: Accepted

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

A.sort()
n = N//2
if N%2 != 0:
    ans1,ans2,ans = 0,0,0
    ar1,ar2 = A[:n],A[n+1:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    ar.append(A[n])
    for i in range(N-1):
        ans1 += abs(ar[i]-ar[i+1])
    ar = [A[n]]+ar[:-1]
    for i in range(N-1):
        ans2 += abs(ar[i]-ar[i+1])
    ans = max(ans1,ans2)
else:
    ans = 0
    ar1,ar2 = A[:n],A[n:]
    ar = []
    for i in range(n):
        ar.append(ar2[i])
        ar.append(ar1[i])
    for i in range(N-1):
        ans += abs(ar[i]-ar[i+1])
 
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
A = sorted(A)
B = list(reversed(A))
ans = -1
#print(A)
#print(B)
if(N % 2 == 0):
    k = N//2
    typeN = -(2*sum(A[:k])+A[k]) + (2*sum(B[:k])+B[k])
    ans = typeN
else:
    k = N//2
    typeW = (2*sum(B[:k-1])+B[k-1]+B[k]) - (2*sum(A[:k]))
    typeM = (2*sum(B[:k])) - (2*sum(A[:k-1])+A[k-1]+A[k])
    ans = max(typeW,typeM)
print(ans)

Submission status: Accepted

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

omi=a.popleft()
oma=a.pop()
ans=abs(oma-omi)
ret=True

while len(a)>1:
    mi=a.popleft()
    ma=a.pop()

    if ret:
        mi,ma=ma,mi

    ans+=abs(omi-mi)+abs(oma-ma)
    omi,oma=mi,ma
    ret = not ret

if len(a)==1:
    aa=a.pop()
    ans+=max(abs(omi-aa),abs(oma-aa))

print(ans)

Submission status: Accepted

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

A.sort()

l = 0
r = N-1
p = []
ans = 0
while l < r:
    p.append(A[r])
    p.append(A[l])
    r -= 1
    l += 1
if N % 2 == 1:
    p.append(A[r])

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

ans = sum(q)-min(q)

l = 0
r = N-1
p = []
while l < r:
    p.append(A[l])
    p.append(A[r])
    r -= 1
    l += 1
if N % 2 == 1:
    p.append(A[r])

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

print(max(ans,sum(q)-min(q)))

Submission status: Accepted

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

a=deque(a)
b=deque([a.popleft()])

i=0
while a:
    if (i//2)%2==0:
        if i%2==0:
            deque.append(b,a.pop())
        else:
            deque.appendleft(b,a.pop())
    else:
        if i%2==0:
            deque.append(b,a.popleft())
        else:
            deque.appendleft(b,a.popleft())
    
    i+=1
ans=0
for i in range(1,n):
    ans+=abs(b[i]-b[i-1])

c=deque(c)
b=deque([c.pop()])

i=0
while c:
    if (i//2)%2==0:
        if i%2==0:
            deque.append(b,c.popleft())
        else:
            deque.appendleft(b,c.popleft())
    else:
        if i%2==0:
            deque.append(b,c.pop())
        else:
            deque.appendleft(b,c.pop())
    
    i+=1
cnt=0
for i in range(1,n):
    cnt+=abs(b[i]-b[i-1])
ans=max(ans,cnt)

print(ans)

Submission status: Accepted

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

from collections import*
A.sort()
ans1=deque()
ans1.append(A[0])
i=j=1
while i<=N-j:
    if i<=N-j:
        ans1.append(A[-j])
        j+=1
    if i<=N-j:
        ans1.appendleft(A[-j])
        j+=1
    if i<=N-j:
        ans1.append(A[i])
        i+=1
    if i<=N-j:
        ans1.appendleft(A[i])
        i+=1
ans1=list(ans1)
ans1=sum(abs(x-y)for x,y in zip(ans1,ans1[1:]))

A=A[::-1]
ans2=deque()
ans2.append(A[0])
i=j=1
while i<=N-j:
    if i<=N-j:
        ans2.append(A[-j])
        j+=1
    if i<=N-j:
        ans2.appendleft(A[-j])
        j+=1
    if i<=N-j:
        ans2.append(A[i])
        i+=1
    if i<=N-j:
        ans2.appendleft(A[i])
        i+=1
ans2=list(ans2)
ans2=sum(abs(x-y)for x,y in zip(ans2,ans2[1:]))

print(max(ans1,ans2))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def run():
    N, *A = map(int, read().split())
    A.sort()
    if not N % 2:
        Al = A[:N // 2]
        Ah = A[N // 2:]
        ans = 0
        ans += 2 * sum(Ah)
        ans -= Ah[0]
        ans -= 2 * sum(Al)
        ans += Al[-1]
        print(ans)

    else:
        # ans1
        Al = A[:N // 2]
        Ah = A[N // 2:]
        #print(Al, Ah)
        ans1 = 0
        ans1 += 2 * sum(Ah)
        ans1 -= sum(Ah[:2])
        ans1 -= sum(Al) * 2

        # ans2
        Al = A[:N // 2 + 1]
        Ah = A[N // 2 + 1:]
        #print(Al, Ah)
        ans2 = 0
        ans2 += 2 * sum(Ah)
        ans2 -= sum(Al) * 2
        ans2 += sum(Al[-2:])
        print(max(ans1, ans2))

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
# print(a)
a.sort()
n2 = n//2
if n % 2 == 0:
    print(sum(a[n2:])*2 - sum(a[:n2])*2 - a[n2]+a[n2-1])
else:
    
    ans1 = sum(a[n2+1:])*2 - sum(a[:n2+1])*2 + a[n2-1]+a[n2]
    
    ans2 = sum(a[n2:])*2 - sum(a[:n2])*2 - a[n2]-a[n2+1]
    print(max(ans1, ans2))

Submission status: Accepted

Solution code:
N=int(input())
M=N//2
l=[int(input()) for i in range(N)]
l.sort()
if N%2==0:
   print(-2*sum(l[0:M-1])-l[M-1]+l[M]+2*sum(l[M+1:]))
else:
   pt1=-2*sum(l[:M-1])-l[M-1]-l[M] +2*sum(l[M+1:])
   pt2=-2*sum(l[:M]) +l[M] + l[M+1] +2*sum(l[M+2:])
   print(max(pt1,pt2))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = list(int(input()) for _ in range(N))

ans = 0
d = deque(sorted(A))
while len(d) > 3:
    ans += 2*(deque.pop(d)-deque.popleft(d))
if len(d) == 2:
    ans += deque.pop(d)-deque.popleft(d)
else:
    a, b, c = d
    ans += max(b+c-2*a, -a-b+2*c) 
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    # (1) N = 2n + 1
    #     (1-1): p1 >= p2 <= p3 >= ... <= pN
    #         各pの隣同士の差の和における係数について考えると
    #         2: n-1個（両端以外の山）、1: 2個（両端）、-2: n個（谷）。
    #     (1-2): p1 <= p2 >= p3 <= ... >= pN
    #         各pの隣同士の差の和における係数について考えると
    #         2: n個（山）、-1: 2個（両端）、-2: n-1個（両端以外の谷）。
    if N % 2 == 1:
        n = N // 2
        ans_1 = 0
        for i, a in enumerate(A):
            coef = 2
            if i < n:  # 小さい順で1～n番目は係数-2
                coef = -2
            elif i < n + 2:  # 小さい順でn+1～n+2番目は係数1
                coef = 1
            ans_1 += coef * a
        ans_2 = 0
        for i, a in enumerate(A):
            coef = 2
            if i < n - 1:  # 小さい順で1～n-1番目は係数-2
                coef = -2
            elif i < n + 1:  # 小さい順でn～n+1番目は係数1
                coef = -1
            ans_2 += coef * a
        print(max(ans_1, ans_2))
    # (2) N = 2n
    #     p1 >= p2 <= p3 >= ... >= pN
    #     各pの隣同士の差の和における係数について考えると
    #     2: n-1個（左端以外の山）、1: 1個（左端）、-1: 1個（右端）、-2: n-1個（谷）。
    else:
        n = N // 2
        ans = 0
        for i, a in enumerate(A):
            coef = 2
            if i < n - 1:  # 小さい順で1～n-1番目は係数-2
                coef = -2
            elif i < n:  # 小さい順でn番目は係数-1
                coef = -1
            elif i < n + 1:  # 小さい順でn+1番目は係数1
                coef = 1
            ans += coef * a
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
import copy
import sys
sys.setrecursionlimit(50000)
N = int(input())
d_1, d_2 = deque([]), deque([])
l = []
for i in range(N):
  l.append(int(input()))
  
l.sort()
l_1, l_2 = copy.copy(l), copy.copy(l)
d_1.append(max(l))
d_2.append(min(l))
l_1.pop()
l_2.pop(0)

def main1(d, l):
  d.appendleft(l[0])
  l.pop(0)
  if l == []:
    return d
  d.append(l[0])
  l.pop(0)
  if l == []:
    return d
  d.appendleft(l[-1])
  l.pop()
  if l == []:
    return d
  d.append(l[-1])
  l.pop()
  if l == []:
    return d
  else:
    return main1(d, l)
  
def main2(d, l):
  d.appendleft(l[-1])
  l.pop()
  if l == []:
    return d
  d.append(l[-1])
  l.pop()
  if l == []:
    return d
  d.appendleft(l[0])
  l.pop(0)
  if l == []:
    return d
  d.append(l[0])
  l.pop(0)
  if l == []:
    return d
  else:
    return main2(d, l)
  
x, y = 0, 0
a = main1(d_1, l_1)
b = main2(d_2, l_2)
for i in range(N-1):
  x += abs(a[i+1]-a[i])
  y += abs(b[i+1]-b[i])
print(max(x, y))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def func1(A):
    ans = 0
    N = len(A)
    m, p = [], []
    for i in range(N):
        if i < N // 2:
            m.append(A[i])
        else:
            p.append(A[i])

    ans -= sum(m) * 2
    ans += sum(p) * 2

    if N % 2 == 0:
        ans += m[-1]
        ans -= p[0]
    else:
        ans -= p[0]
        ans -= p[1]

    return ans


def func2(A):
    ans = 0
    N = len(A)
    m, p = [], []
    for i in range(N):
        if i < N // 2 + 1:
            m.append(A[i])
        else:
            p.append(A[i])

    ans -= sum(m) * 2
    ans += sum(p) * 2

    if N % 2 == 0:
        ans += m[-1]
        ans -= p[0]
    else:
        ans += m[-1]
        ans += m[-2]

    return ans


def solve(A):
    return max(func1(A[:]), func2(A[:]))


def check(A):
    ans = 0
    for p in permutations(A):
        tmp = 0
        for i in range(1, len(p)):
            tmp += abs(p[i] - p[i - 1])

        ans = max(ans, tmp)
    return ans


def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    A.sort()

    if N < 5:
        print(check(A))
    else:
        print(solve(A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

import sys
# sys.setrecursionlimit(100000)
from collections import deque


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = []
    for _ in range(n):
        A.append(input_int())
    A = sorted(A)
    dq = deque(A)
    ans = 0

    # 貪欲に最も差分が大きい組み合わせを使っていく
    left = dq.popleft()
    right = dq.pop()
    ans = abs(right - left)

    while dq:
        l = dq[0]
        r = dq[-1]
        if abs(left - l) == max(abs(left - l), abs(right - l), abs(left - r), abs(right - r)):
            ans += abs(left - l)
            left = l
            dq.popleft()
        elif abs(left - r) == max(abs(left - l), abs(right - l), abs(left - r), abs(right - r)):
            ans += abs(left - r)
            left = r
            dq.pop()
        elif abs(right - l) == max(abs(left - l), abs(right - l), abs(left - r), abs(right - r)):
            ans += abs(right - l)
            right = l
            dq.popleft()
        elif abs(right - r) == max(abs(left - l), abs(right - l), abs(left - r), abs(right - r)):
            ans += abs(right - r)
            right = r
            dq.pop()

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
work = []
ans = 0
if N % 2 == 1:
    before = A[:N // 2]
    after = A[N // 2 + 1:]
    median = A[N // 2]
    for i in range(N // 2):
        work.append(after[i])
        work.append(before[i])
    work.append(median)
    tmp1 = 0
    tmp2 = 0
    for i in range(N - 1):
        tmp1 += abs(work[i] - work[i + 1])
    t = work.pop()
    work.insert(0, t)
    for i in range(N - 1):
        tmp2 += abs(work[i] - work[i + 1])
    ans = max(tmp1, tmp2)

else:
    before = A[:N // 2]
    after = A[N // 2:]
    for i in range(N // 2):
        work.append(after[i])
        work.append(before[i])
    for i in range(N - 1):
        ans += abs(work[i] - work[i + 1])
print(ans)

Submission status: Accepted

Solution code:
import math
n = int(input())

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

A.sort()

half = math.floor(n/2)
if n ==2:
    print(A[1]-A[0])
else:
    half_A = A[half]
    dif = A[half+1] - half_A*2 +A[half-1]
    if (n%2 == 1) & (dif>0):
        total = sum(A[half+1:])*2 - sum(A[:half-1])*2 -A[half] - A[half-1]
    elif (n % 2 == 1) & (dif<=0):
        total = sum(A[half+2:])*2 - sum(A[:half])*2 + A[half] + A[half+1]
    else:
        total = sum(A[half+1:])*2 - sum(A[:half-1])*2 -A[half-1] + A[half]
    
    print(total)

Submission status: Accepted

Solution code:
# C - Align
N = int(input())
A = [0]+[int(input()) for _ in range(N)]
A = sorted(A)
ans = 0
if N%2==0:
    i = 1
    while i<N//2:
        ans -= 2*A[i]
        i += 1
    ans -= A[i]
    i += 1
    ans += A[i]
    i += 1
    while i<=N:
        ans += 2*A[i]
        i += 1
else:
    i = 1
    while i<N//2:
        ans -= 2*A[i]
        i += 1
    ans -= A[i]
    i += 1
    ans -= A[i]
    i += 1
    while i<=N:
        ans += 2*A[i]
        i += 1
    tmp = 0
    A = [0]+sorted(A[1:], reverse=True)
    i = 1
    while i<N//2:
        tmp += 2*A[i]
        i += 1
    tmp += A[i]
    i += 1
    tmp += A[i]
    i += 1
    while i<=N:
        tmp -= 2*A[i]
        i += 1
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    A.sort()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    if N == 2:
        print(abs(A[0] - A[1]))
        return

    A.sort()

    q = collections.deque(A)

    ans = 0
    i = 0
    c = [q.popleft(), q.pop()]
    ans += abs(c[0] - c[1])
    while q:
        if len(q) >= 2:
            a = q.popleft()
            b = q.pop()
            al = abs(a - c[0])
            ar = abs(a - c[1])
            bl = abs(b - c[0])
            br = abs(b - c[1])
            ma = max([al, ar, bl, br])
            ans += ma
            if ma == al:
                c[0] = a
                q.append(b)
            elif ma == ar:
                c[1] = a
                q.append(b)
            elif ma == bl:
                c[0] = b
                q.appendleft(a)
            else:
                c[1] = b
                q.appendleft(a)
        else:
            a = q.pop()
            ans += max(abs(c[0] - a), abs(c[1] - a))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#================================================
from collections import deque

N=int(input())
A=[0]*N
for i in range(N):
    A[i]=int(input())
A.sort()
#=====================
Q=deque(range(1,N))
R=deque([0])
for i in range((N-1)//2):
    if i%2:
        x=Q.popleft()
        y=Q.popleft()
    else:
        x=Q.pop()
        y=Q.pop()

    R.appendleft(x)
    R.append(y)

if Q:
    x=Q.pop()
    R.appendleft(x)

X=[0]*N
Y=[0]*N
for i in range(N):
    X[i]=A[R[i]]
    Y[i]=A[-(R[i]+1)]

alpha=0
beta=0

for i in range(N-1):
    alpha+=abs(X[i+1]-X[i])
    beta +=abs(Y[i+1]-Y[i])
print(max(alpha,beta))

Submission status: Accepted

Solution code:
n = int(input())
A = [int(input()) for _ in range(n)]
A = sorted(A,reverse=True)

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

Submission status: Accepted

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

from collections import deque
from typing import Deque

A.sort()

DL = Deque(A)
DS = Deque(A)

LL = [0 for _ in range(N)]
LS = [0 for _ in range(N)]


if N % 2 == 0:

    for i in range(1, N, 2):
        LS[i] = DS.popleft()
        LL[i] = DL.pop()
    for j in range(0, N, 2):
        LS[j] = DS.popleft()
        LL[j] = DL.pop()

else:
    for i in range(1, N):
        if i % 2 == 1:
            LS[i] = DS.pop()
            LL[i] = DL.popleft()
        else:
            LS[i] = DS.popleft()
            LL[i] = DL.pop()

    LS[0] = DS.pop()
    LL[0] = DL.pop()

ansS = 0
ansL = 0
for i in range(1, N, 2):
    if i == N - 1:
        ansS += abs(LS[i] - LS[i-1])
        ansL += abs(LL[i] - LL[i-1])
    else:
        ansS += abs(LS[i] - LS[i-1])
        ansS += abs(LS[i] - LS[i+1])

        ansL += abs(LL[i] - LL[i-1])
        ansL += abs(LL[i] - LL[i+1])

print(max(ansS, ansL))

Submission status: Accepted

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

if n%2 == 0:
    ans = 2*(sum(a[n//2:])-sum(a[:n//2]))+a[n//2-1]-a[n//2]
else:
    ans = 2*(sum(a[n//2+1:])-sum(a[:n//2]))
    ans -= min(a[n//2+1]-a[n//2], a[n//2]-a[n//2-1])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    lis=LI2()
    lis.sort()
    ans=0
    if n%2==0:
        x=n//2
        for i in range(x-1):
            ans+=2*(lis[n-i-1]-lis[i])
        ans+=lis[n-x]-lis[x-1]
        print(ans)
    else:
        if n==1:
            print(0)
            sys.exit()
        x=n//2
        ans1=0  
        ans2=0
        for i in range(x):
            ans1+=2*lis[n-i-1]
            ans2-=2*lis[i]
        for i in range(x-1):
            ans1-=2*lis[i]
            ans2+=2*lis[n-i-1]
        ans1-=lis[x]+lis[x-1]
        ans2+=lis[x]+lis[x+1]
        #print(ans1,ans2)
        print(max(ans1,ans2))
if __name__=="__main__":
    main()

Submission status: Accepted

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

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

for i in range(N):
    p = 1 if i in [0, N-1] else 2
    coef1.append(p*(1 if i%2==0 else -1))
    coef2.append(p*(-1 if i%2==0 else 1))

A.sort()
coef1.sort()
coef2.sort()
ans = max(sum(Ai*p for Ai, p in zip(A, coef1)), sum(Ai*p for Ai, p in zip(A, coef2)))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
a=deque(sorted([int(input()) for _ in range(n)]))
b=deque([a.pop()])
i=0
while a:
  if max(abs(a[-1]-b[-1]),abs(a[-1]-b[0]),abs(a[0]-b[-1]),abs(a[0]-b[0]))==abs(a[-1]-b[-1]):
    b.append(a.pop())
  elif max(abs(a[-1]-b[-1]),abs(a[-1]-b[0]),abs(a[0]-b[-1]),abs(a[0]-b[0]))==abs(a[-1]-b[0]):
    b.appendleft(a.pop())
  elif max(abs(a[-1]-b[-1]),abs(a[-1]-b[0]),abs(a[0]-b[-1]),abs(a[0]-b[0]))==abs(a[0]-b[0]):
    b.appendleft(a.popleft())
  else:
    b.append(a.popleft())
ans=0
for i in range(n-1):
  ans+=abs(b[i]-b[i+1])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

tmpl=a.popleft()
tmpr=tmpl
ans=0
i=0

while len(a)>0:
    #0 大きいほうから
    if i%4==0:
        tmp=a.pop()
        ans+=abs(tmpl-tmp)
        tmpl=tmp

    #1 大きいほうから
    elif i%4==1:
        tmp=a.pop()
        ans+=abs(tmpr-tmp)
        tmpr=tmp

    #2 小さいほうから
    elif i%4==2:
        tmp=a.popleft()
        ans+=abs(tmpl-tmp)
        tmpl=tmp


    #3 小さいほうから
    elif i%4==3:
        tmp=a.popleft()
        ans+=abs(tmpr-tmp)
        tmpr=tmp

    i+=1

res=ans
import copy
d.sort(reverse=True)
a= deque(copy.deepcopy(d))

tmpl=a.popleft()
tmpr=tmpl
ans=0
i=0

while len(a)>0:
    #0 大きいほうから
    if i%4==0:
        tmp=a.pop()
        ans+=abs(tmpl-tmp)
        tmpl=tmp

    #1 大きいほうから
    elif i%4==1:
        tmp=a.pop()
        ans+=abs(tmpr-tmp)
        tmpr=tmp

    #2 小さいほうから
    elif i%4==2:
        tmp=a.popleft()
        ans+=abs(tmpl-tmp)
        tmpl=tmp


    #3 小さいほうから
    elif i%4==3:
        tmp=a.popleft()
        ans+=abs(tmpr-tmp)
        tmpr=tmp

    i+=1

print(max(ans,res))