Problem:


Score : 400 points

Problem Statement

You are given N integers; the i-th of them is A_i.
Find the maximum possible sum of the absolute differences between the adjacent elements after arranging these integers in a row in any order you like.

Constraints

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the maximum possible sum of the absolute differences between the adjacent elements after arranging the given integers in a row in any order you like.

Sample Input 1

5
6
8
1
2
3

Sample Output 1

21

When the integers are arranged as 3,8,1,6,2, the sum of the absolute differences between the adjacent elements is |3 - 8| + |8 - 1| + |1 - 6| + |6 - 2| = 21. This is the maximum possible sum.

Sample Input 2

6
3
1
4
1
5
9

Sample Output 2

25

Sample Input 3

3
5
5
1

Sample Output 3

8



Sample input:
5
6
8
1
2
3


Sample output:
21

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


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

    A.sort()
    ans = 0
    if N % 2 == 1:
        # center is minimum
        a = deque(A[1:])
        b = deque([A[0]])
        nxt = "r"
        while a:
            if nxt == "r":
                nxt = "l"
                x = a.pop()
                y = a.pop()
                b.appendleft(x)
                b.append(y)
            else:
                nxt = "r"
                x = a.popleft()
                y = a.popleft()
                b.appendleft(x)
                b.append(y)
        diff = sum(abs(b[i + 1] - b[i]) for i in range(N - 1))
        ans = max(ans, diff)
        # center is maximum
        a = deque(A[::-1][1:])
        b = deque([A[-1]])
        nxt = "r"
        while a:
            if nxt == "r":
                nxt = "l"
                x = a.pop()
                y = a.pop()
                b.appendleft(x)
                b.append(y)
            else:
                nxt = "r"
                x = a.popleft()
                y = a.popleft()
                b.appendleft(x)
                b.append(y)
        diff = sum(abs(b[i + 1] - b[i]) for i in range(N - 1))
        ans = max(ans, diff)

    else:
        # center is minimum
        a = deque(A[1:])
        b = deque([A[0]])
        nxt = "r"
        while a:
            if len(a) == 1:
                rem = a.pop()
                break
            if nxt == "r":
                nxt = "l"
                x = a.pop()
                y = a.pop()
                b.appendleft(x)
                b.append(y)
            else:
                nxt = "r"
                x = a.popleft()
                y = a.popleft()
                b.appendleft(x)
                b.append(y)
        diff = sum(abs(b[i + 1] - b[i]) for i in range(N - 2))
        diff += max(abs(rem - b[0]), abs(rem - b[-1]))
        ans = max(ans, diff)

        # center is maximum
        a = deque(A[::-1][1:])
        b = deque([A[-1]])
        nxt = "r"
        while a:
            if len(a) == 1:
                rem = a.pop()
                break
            if nxt == "r":
                nxt = "l"
                x = a.pop()
                y = a.pop()
                b.appendleft(x)
                b.append(y)
            else:
                nxt = "r"
                x = a.popleft()
                y = a.popleft()
                b.appendleft(x)
                b.append(y)
        diff = sum(abs(b[i + 1] - b[i]) for i in range(N - 2))
        diff += max(abs(rem - b[0]), abs(rem - b[-1]))
        ans = max(ans, diff)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(int(readline()) for _ in range(N))
    A.sort(reverse=True)
    B = []
    C = []
    lb = 0
    rb = -1
    lc = 0
    rc = -1
    for i in range(N):
        if i % 2 == 0:
            B.append(A[lb])
            lb += 1
            C.append(A[rc])
            rc -= 1
        else:
            B.append(A[rb])
            rb -= 1
            C.append(A[lc])
            lc += 1
    ansb = 0
    for i in range(N - 2):
        ansb += abs(B[i] - B[i + 1])
    ansb += max(abs(B[0] - B[-1]), abs(B[-2] - B[-1]))

    ansc = 0
    for i in range(N - 2):
        ansc += abs(C[i] - C[i + 1])
    ansc += max(abs(C[0] - C[-1]), abs(C[-2] - C[-1]))


    print(max(ansb,ansc))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a=sorted(a)

from collections import deque

d=deque(a)

ans=deque([d.pop()])

for i in range(n-1):
    if i%2==0:
        p=d.popleft()
    else:
        p=d.pop()
        
    if abs(p-ans[0])>=abs(p-ans[-1]):
        ans.appendleft(p)
    else:
        ans.append(p)


dif = 0

for j in range(n-1):
    dif += abs(ans[j+1] - ans[j])

d=deque(a)
ans=deque([])

for i in range(n):
    if i==n-1:
        z=d.pop()

        if abs(z-ans[0])>abs(z-ans[-1]):
            ans.appendleft(z)
        else:
            ans.append(z)
    else:
        if i%2==0:
            p=d.pop()
            ans.append(p)
        else:
            q=d.popleft()
            ans.append(q)

dif2 = 0
for j in range(n-1):
    dif2 += abs(ans[j+1] - ans[j])

print(max(dif,dif2))

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a = sorted(int(input()) for _ in range(n))
d = deque(a)
l = deque([])
bit = 0
if len(d)%2==0:
    while d:
        dmi = d.popleft()
        dma = d.pop()
        if bit==1:
            l.appendleft(dmi)
            l.append(dma)
            bit = 0
        else:
            l.append(dmi)
            l.appendleft(dma)
            bit = 1
else:
    while len(d)!=1:
        dmi = d.popleft()
        dma = d.pop()
        if bit==1:
            l.appendleft(dmi)
            l.append(dma)
            bit = 0
        else:
            l.append(dmi)
            l.appendleft(dma)
            bit = 1
    last = d.pop()
    if abs(l[0]-last)<abs(l[-1]-last):
        l.append(last)
    else:
        l.appendleft(last)
ans = 0
for i in range(len(l)-1):
  ans += abs(l[i+1] - l[i])
  
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
A = [int(input()) for _ in range(N)]
A = sorted(A)

def solve(pat):
    ans = []
    for i in range(N // 2):
        if pat:
            ans.append(A[N - 1 - i])
            ans.append(A[i])
        else:
            ans.append(A[i])
            ans.append(A[N - 1 - i])
    if N % 2 == 1:
        ans.append(A[N // 2])

    res = 0
    for i in range(1, N - 1):
        res += abs(ans[i] - ans[i - 1])
    x = abs(ans[-2] - ans[-1])
    y = abs(ans[-1] - ans[0])
    return (max(x, y) + res)

print(max(solve(True), solve(False)))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

        
def main():
    import sys

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

    n = int(input())
    a = [int(input()) for _ in range(n)]
    a.sort(reverse=True)
    if n%2 == 0:
        ans = 2*(sum(a[:n//2])-sum(a[n//2:]))
        ans += a[n//2]-a[n//2-1]
    else:
        ans = 2*(sum(a[:n//2])-sum(a[n//2+1:]))
        tmp = max(a[n//2]-a[n//2-1], a[n//2+1]-a[n//2])
        ans += tmp
    print(ans)



                
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = []
for i in range(n):
    x = int(input())
    a.append(x)
data1 = []
data2 = []
a = sorted(a)
for i in range(n // 2):
    data1.append(a[n - i - 1])
    data2.append(a[i])
    if len(data1) + 1 != n:
        data1.append(a[i])
        data2.append(a[n - i - 1])
index = n // 2
if n % 2 == 0:
    index -= 1

def set_p(data):
    if abs(data1[0] - a[index]) > abs(data1[-1] - a[index]):
        p = 0
    else:
        p = n
    return p
p1 = set_p(data1)
p2 = set_p(data2)
data1.insert(p1, a[index]) 
data2.insert(p2, a[index])
ans = 0
def calc_ans(data):
    ans = 0
    for i in range(1, n):
        ans += abs(data[i] - data[i - 1])
    return ans
    
print(max(calc_ans(data1), calc_ans(data2)))

Submission status: Accepted

Solution code:
from collections import deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = [read_int() for _ in range(N)]
    A.sort()
    i, j = 0, N-2
    left = right = N-1 # points to left and right side of array
    answer = 0
    while i <= j:
        d, i, j, left, right = max([(abs(A[left]-A[i]), i+1, j, i, right),
                                    (abs(A[left]-A[j]), i, j-1, j, right),
                                    (abs(A[right]-A[i]), i+1, j, left, i),
                                    (abs(A[right]-A[j]), i, j-1, left, j)])
        answer += d
    return answer


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

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
A = sorted([int(input()) for _ in range(N)])
B = sorted(A[::1],reverse = 1)
qA = collections.deque(A)
qB = collections.deque(B)
Al = []
Bl = []
i = 1
while qA:
    if i:
        Al.append(qA.pop())
        Bl.append(qB.pop())
    else:
        Al.append(qA.popleft())
        Bl.append(qB.popleft())
    i = (i+1)%2
Al = [Al[-1]]+Al[:-1:]
Bl = [Bl[-1]]+Bl[:-1:]
cntA=0
cntB=0
for i in range(N-1):
    cntA += abs(Al[i+1]-Al[i])
    cntB += abs(Bl[i+1]-Bl[i])
print(max(cntA,cntB))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = [I() for _ in range(N)]
    A.sort()

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

cand1 = [0] * n
cand2 = [0] * n
for i in range(n - 1):
    if i % 2 == 0:
        cand1[i] -= 1
        cand1[i + 1] += 1
        cand2[i] += 1
        cand2[i + 1] -= 1
    else:
        cand1[i] += 1
        cand1[i + 1] -= 1
        cand2[i] -= 1
        cand2[i + 1] += 1

cand1.sort()
cand2.sort()
a.sort()

ans = max(
    sum(a[i] * cand1[i] for i in range(n)),
    sum(a[i] * cand2[i] for i in range(n)),
)
print(ans)

Submission status: Accepted

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

a.sort()
a = deque(a)

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

ans = 0
for _ in range(n - 1):
    x = max(
        abs(a[0] - b[0]),
        abs(a[0] - b[-1]),
        abs(a[-1] - b[0]),
        abs(a[-1] - b[-1]),
    )
    if x == abs(a[0] - b[0]):
        b.appendleft(a.popleft())
    elif x == abs(a[0] - b[-1]):
        b.append(a.popleft())
    elif x == abs(a[-1] - b[0]):
        b.appendleft(a.pop())
    else:  # x == abs(a[-1] - b[-1]):
        b.append(a.pop())
    ans += x

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

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

    def calc1():
        b = deque(a)

        que = deque()
        que.append(b.popleft())

        while b:
            if len(b) >= 2:
                que.append(b.pop())
                que.appendleft(b.pop())
            elif len(b) == 1:
                if abs(que[0] - b[0]) > abs(que[-1] - b[0]):
                    que.appendleft(b.pop())
                else:
                    que.append(b.pop())
            if len(b) >= 2:
                que.append(b.popleft())
                que.appendleft(b.popleft())
            elif len(b) == 1:
                if abs(que[0] - b[0]) > abs(que[-1] - b[0]):
                    que.appendleft(b.popleft())
                else:
                    que.append(b.popleft())
        score = 0
        prev = que[0]
        for x in que:
            score += abs(x - prev)
            prev = x
        return score

    def calc2():
        b = deque(a)

        que = deque()
        que.append(b.pop())

        while b:
            if len(b) >= 2:
                que.append(b.popleft())
                que.appendleft(b.popleft())
            elif len(b) == 1:
                if abs(que[0] - b[0]) > abs(que[-1] - b[0]):
                    que.appendleft(b.popleft())
                else:
                    que.append(b.popleft())
            if len(b) >= 2:
                que.append(b.pop())
                que.appendleft(b.pop())
            elif len(b) == 1:
                if abs(que[0] - b[0]) > abs(que[-1] - b[0]):
                    que.appendleft(b.pop())
                else:
                    que.append(b.pop())
        score = 0
        prev = que[0]
        for x in que:
            score += abs(x - prev)
            prev = x
        return score

    print(max(calc1(), calc2()))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())

a = []

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

a.sort(reverse=True)

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

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

    ans = max(ans1, ans2)

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

print(ans)

Submission status: Accepted

Solution code:
from collections import *
from copy import *
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
a.sort()
a=deque(a)
b=deepcopy(a)
bb=deque()
bb.append(b.pop())
aa=deque()
aa.append(a.popleft())
while a:
    aa.append(a.pop())
    if a:
        aa.appendleft(a.pop())   
    if a:
        aa.append(a.popleft())
    if a:
        aa.appendleft(a.popleft())
ans=0
aa=list(aa)
while b:
    bb.append(b.popleft())
    if b:
        bb.appendleft(b.popleft())
    if b:
        bb.append(b.pop())
    if b:
        bb.appendleft(b.pop())
bb=list(bb)
ans1=0
for i in range(n-1):
    ans+=abs(aa[i]-aa[i+1])
    ans1+=abs(bb[i]-bb[i+1])
print(max(ans1,ans))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
from collections import deque
n = int(input())
li_a = []
for i in range(n):
  li_a.append(int(input()))
m1 = []
M1 = []
m2 = []
M2 = []
for i in li_a:
    heappush(m1, i)
    heappush(M1, -i)
    heappush(m2, i)
    heappush(M2, -i)
l1 = deque()
l2 = deque()
if n % 2 == 0:
    l1.append(-heappop(M1))
    l2.append(heappop(m2))
    while True:
        l1.append(heappop(m1))
        l2.append(-heappop(M2))
        if len(l1) == n:
            break
        l1.appendleft(heappop(m1))
        l2.appendleft(-heappop(M2))
        if len(l1) == n:
            break
        else:
            l1.append(-heappop(M1))
            l2.append(heappop(m2))
            if len(l1) == n:
                break
            l1.appendleft(-heappop(M1))
            l2.appendleft(heappop(m2))
            if len(l1) == n:
                break
if n % 2 == 1:
    l1.append(-heappop(M1))
    l2.append(heappop(m2))
    while True:
        l1.append(heappop(m1))
        l2.append(-heappop(M2))
        l1.appendleft(heappop(m1))
        l2.appendleft(-heappop(M2))
        if len(l1) == n:
            break
        else:
            l1.append(-heappop(M1))
            l1.appendleft(-heappop(M1))
            l2.append(heappop(m2))
            l2.appendleft(heappop(m2))
            if len(l1) == n:
                break
ans1 = 0
ans2 = 0
for i in range(n-1):
    ans1 += abs(l1[i+1]-l1[i])
    ans2 += abs(l2[i+1]-l2[i])
print(max(ans1, ans2))

Submission status: Accepted

Solution code:
N=int(input())

alist=[]
for _ in range(N):
  a=int(input())
  alist.append(a)
alist.sort()
#print(alist)

if N%2==0:
  answer=0
  for i in range(N//2-1):
    a=alist.pop()
    answer+=2*a
  answer+=alist.pop()
  answer-=alist.pop()
  for i in range(N//2-1):
    a=alist.pop()
    answer-=2*a
    
  print(answer)
else:
  ans1=0
  alist_copy=alist[:]
  for i in range(N//2-1):
    a=alist_copy.pop()
    ans1+=2*a
  ans1+=alist_copy.pop()
  ans1+=alist_copy.pop()
  for i in range(N//2):
    a=alist_copy.pop()
    ans1-=2*a
    
  ans2=0
  alist_copy=alist[:]
  for i in range(N//2):
    a=alist_copy.pop()
    ans2+=2*a
  ans2-=alist_copy.pop()
  ans2-=alist_copy.pop()
  for i in range(N//2-1):
    a=alist_copy.pop()
    ans2-=2*a
    
  print(max(ans1,ans2))

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

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

a.sort()
qa = deque(a)
qb = deque()

for i in range(len(qa)):
    if i % 4 == 0:
        qb.appendleft(qa.popleft())
    elif i % 4 == 1:
        qb.append(qa.pop())
    elif i % 4 == 2:
        qb.appendleft(qa.pop())
    else:
        qb.append(qa.popleft())

ans = 0
reg = inf
for i in range(len(qb)):
    if i < len(qb) - 1:
        tmp = abs( qb[i+1] - qb[i] )
    else:
        tmp = abs( qb[0] - qb[i])
    ans += tmp
    reg = min(reg, tmp)
ans -= reg
print(ans)

Submission status: Accepted

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

l=a.popleft() 
r=l
count=0
ans=0
while len(a)>0:
  if count%4==0:
    temp=a.pop()
    ans+=abs(temp-l)
    l=temp
  elif count%4==1:
    temp=a.pop()
    ans+=abs(temp-r)
    r=temp
  elif count%4==2:
    temp=a.popleft()
    ans+=abs(l-temp)
    l=temp
  elif count%4==3:
    temp=a.popleft()
    ans+=abs(r-temp)
    r=temp
  count+=1
  
l=b.pop() 
r=l
count=0
ans2=0
while len(b)>0:
  if count%4==2:
    temp=b.pop()
    ans2+=abs(temp-l)
    l=temp
  elif count%4==3:
    temp=b.pop()
    ans2+=abs(temp-r)
    r=temp
  elif count%4==0:
    temp=b.popleft()
    ans2+=abs(l-temp)
    l=temp
  elif count%4==1:
    temp=b.popleft()
    ans2+=abs(r-temp)
    r=temp
  count+=1
print(max(ans, ans2))

Submission status: Accepted

Solution code:
n,*a = map(int,open(0).read().split())
a.sort()
l = 0
r = n-1
b = [a[0],a[n-1]]
ans = abs(b[0]-b[1])
while(r-l>1):
  c = max([(abs(a[i]-b[j]),i,j) for i in (l+1,r-1) for j in (0,1)])
  ans += c[0]
  b[c[2]] = a[c[1]]
  if c[1] == l+1:
    l += 1
  else:
    r -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


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

    A.sort()
    d = deque(A)
    min_A = d.popleft()
    max_A = d.pop()
    ans = max_A - min_A
    v1 = min_A
    v2 = max_A
    while d:
        if len(d) == 1:
            v = d.pop()
            ans += max(abs(v1 - v), abs(v2 - v))
        else:
            v_min = d[0]
            v_max = d[-1]
            diff = 0
            is_popleft = None
            if diff < abs(v1 - v_min):
                diff = abs(v1 - v_min)
                next_v1 = v_min
                next_v2 = v2
                is_popleft = True
            if diff < abs(v2 - v_min):
                diff = abs(v2 - v_min)
                next_v1 = v_min
                next_v2 = v1
                is_popleft = True
            if diff < abs(v1 - v_max):
                diff = abs(v1 - v_max)
                next_v1 = v_max
                next_v2 = v2
                is_popleft = False
            if diff < abs(v2 - v_max):
                diff = abs(v2 - v_max)
                next_v1 = v_max
                next_v2 = v1
                is_popleft = False
            if is_popleft is None:
                next_v1 = v_min
                next_v2 = v2
                is_popleft = True
            ans += diff
            v1, v2 = next_v1, next_v2
            if is_popleft:
                d.popleft()
            else:
                d.pop()

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = [int(input()) for _ in range(n)]
	al.sort()
	l = 1
	r = n-1
	ret = 0
	stl=al[0]
	str=al[0]
	while l <= r:
		g = [abs(stl - al[l]), abs(stl-al[r]), abs(str - al[l]), abs(str - al[r])]
		if max(g) == g[0] or max(g) == g[2]:
			up = al[l]
			l+=1
		else:
			up = al[r]
			r -= 1
			
		if max(g) == g[0]:
			stl = up
		elif max(g)==g[2]:
			str = up
		elif max(g)==g[1]:
			stl=up
		else:
			str = up
		ret +=max(g)
	return ret
		
			
		
		
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
import heapq as hq
gcd = math.gcd
n = ni()
A = []
for i in range(n):
    A.append(ni())
A.sort()
A1 = A[:(n+1)//2]
A2 = A[(n+1)//2:]
#print(A1,A2)


if n%2==0:
    print(2*sum(A2) - 2*sum(A1) - A2[0] + A1[-1])

else:
    s1 = 2*sum(A2) - 2*sum(A1) + A1[-1]+A1[-2] #a1がa2より多い場合
    A1 = A[:n//2]
    A2 = A[n//2:]
    s2 = 2*sum(A2)  - 2*sum(A1) -A2[0] -A2[1]#a2がa1より多い場合
    print(max(s1,s2))

Submission status: Accepted

Solution code:
import sys
n = int(input())
A = [int(sys.stdin.readline()) for _ in range(n)]
A.sort(reverse=True)
if n==2:
    print(A[0]-A[1])
elif n%2==0:
    ans = 0
    K = [2]*(max(0,n-2)//2)+[1,-1]+[-2]*(max(0,n-2)//2)
    print(sum([A[i]*K[i] for i in range(n)]))
else:
    K1 = [2]*(max(0,n-2)//2)+[1,1]+[-2]*(max(0,n-2)//2+1)
    K2 = [2]*(max(0,n-2)//2+1)+[-1,-1]+[-2]*(max(0,n-2)//2)
    print(max(sum([A[i]*K1[i] for i in range(n)]),
              sum([A[i]*K2[i] for i in range(n)])))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

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


def solve():
    i = 0
    j = n - 1
    is_odd = n % 2 == 1
    a0 = a[i]
    a1 = a[j]
    s = a[j] - a[i]
    i += 1
    j -= 1
    while i < j:
        s += a[j] - a0
        s += a1 - a[i]
        a0 = a[i]
        a1 = a[j]
        i += 1
        j -= 1
    if is_odd and i == j:
        s += max(a1 - a[i], a[i] - a0)
    return s


print(solve())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(ipt()) for i in range(n)]
    a.sort()
    if n%2:
        ans = a[n//2+1]-a[n//2-1]
        for i in range(n//2-1):
            ans += (a[n-1-i]-a[i])*2
        print(ans+max(a[n//2+1]-a[n//2],a[n//2]-a[n//2-1]))
    else:
        ans = a[n//2]-a[n//2-1]
        for i in range(n//2-1):
            ans += (a[n-1-i]-a[i])*2
        print(ans)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = [int(input()) for _ in range(n)]
a=sorted(A)
# print(n//2)
if n%2:
    print(sum(a[-n//2+1:])*2 - sum(a[:n//2])*2 - min(a[n//2+1]-a[n//2],a[n//2]-a[n//2-1]))
else:
    print(sum(a[n//2+1:])*2 -sum(a[:n//2-1])*2 +a[n//2] -a[n//2-1])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
A.sort()
Aup = deque(A)
Adown = deque(A)
up = deque([])
down = deque([])
up.append(Aup.pop())
down.append(Adown.popleft())

i = 0
while True:
    for i in range(2):
        if i % 2 == 0:
            if up[0] > up[-1]:
                up.appendleft(Aup.popleft())
            else:
                up.append(Aup.popleft())

            if down[0] < down[-1]:
                down.appendleft(Adown.pop())
            else:
                down.append(Adown.pop())

        else:
            if up[0] < up[-1]:
                up.appendleft(Aup.pop())
            else:
                up.append(Aup.pop())

            if down[0] > down[-1]:
                down.appendleft(Adown.popleft())
            else:
                down.append(Adown.popleft())

        if len(Aup) == 0:
            break
    if len(Aup) == 0:
        break
    i += 1
upans = 0
downans = 0
up = list(up)
down = list(down)
for i in range(1,N):
    upans += abs(up[i] - up[i-1])
    downans += abs(down[i] - down[i-1])
print(max(upans,downans))

Submission status: Accepted

Solution code:
def calc_score(li):
    prev = li[0]
    ret = 0
    for el in li:
        ret += abs(el - prev)
        prev = el
    return ret


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

Submission status: Accepted

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

from collections import deque
que = deque(A)

# p1 <= p2 >= p3 <= ...
ans = deque([que.popleft()])
cur = 0
while que:
    if cur % 2 == 0:
        ans.appendleft(que.pop())
        if len(que):
            ans.append(que.pop())
        cur ^= 1
    else:
        ans.appendleft(que.popleft())
        if len(que):
            ans.append(que.popleft())
        cur ^= 1

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

# p1 >= p2 <= p3 >= ...
que = deque(A)
ans = deque([que.pop()])
cur = 1
while que:
    if cur % 2 == 0:
        ans.appendleft(que.pop())
        if len(que):
            ans.append(que.pop())
        cur ^= 1
    else:
        ans.appendleft(que.popleft())
        if len(que):
            ans.append(que.popleft())
        cur ^= 1

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

print(max(res1, res2))

Submission status: Accepted

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

    ans1 = 0
    ans2 = 0
    if N & 1:
        #W型
        a1 = sum(A[N//2+2:])*2+A[N//2+1]+A[N//2]-sum(A[:N//2])*2
        #M型
        a2 = sum(A[N//2+1:])*2-A[N//2]-A[N//2-1]-sum(A[:N//2-1])*2
        print(max(a1,a2))
    else:
        print(sum(A[N//2+1:])*2-sum(A[:N//2-1])*2-A[N//2-1]+A[N//2])










main()