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: Wrong Answer

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

for i in A:
    d.append(i)

ans = deque()
ans.append(d.popleft())

for i in range(len(d)):
    if i % 4 == 2:
        ans.appendleft(d.popleft())
    elif i % 4 == 3:
        ans.append(d.popleft())
    elif i % 4 == 0:
        ans.appendleft(d.pop())
    elif i % 4 == 1:
        ans.append(d.pop())

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

Submission status: Wrong Answer

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

for i in A:
    d.append(i)

ans = deque()
ans.append(d.popleft())

for i in range(len(d)):
    print(i)
    if i % 4 == 2:
        ans.appendleft(d.popleft())
    elif i % 4 == 3:
        ans.append(d.popleft())
    elif i % 4 == 0:
        ans.appendleft(d.pop())
    elif i % 4 == 1:
        ans.append(d.pop())

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

Submission status: Wrong Answer

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

mid = n//2
if n%2 == 0 and (a[-1] - a[mid-1] > a[mid] - a[0]):
    mid -= 1

if a[-1] - a[mid] > a[mid] - a[0]:
    cur = n-1
else:
    cur = 0

l = 0
r = n-1
cnt = 0
cnt += abs(a[mid] - a[cur])

while True:
    if cur > mid:
        if not l == mid:
            cnt += abs(a[cur]-a[l])
            cur = l
            r -= 1
        else:
            break
    elif cur < mid:
        if not r == mid:
            cnt += abs(a[r]-a[cur])
            cur = r
            l += 1
        else:
            break

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(int(input()) for TN in range(0,N))
if N%2==0:
    Small = A[:(N//2)]
    Big   = [A[N//2]]+A[(N//2)+1:][::-1]
    Point = abs(Big[0]-Small[0])
    for TN in range(1,(N//2)):
        Point += abs(Small[TN-1]-Big[TN])+abs(Big[TN]-Small[TN])
else:
    Small = A[:(N//2)]
    Big   = A[(N//2)+1:][::-1]
    Point = abs(Big[0]-Small[0])
    for TN in range(1,(N//2)):
        Point += abs(Small[TN-1]-Big[TN])+abs(Big[TN]-Small[TN])
    Point += max(abs(A[N//2]-Big[0]),abs(Small[(N//2)-1]-A[N//2]))
print(Point)

Submission status: Wrong Answer

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

maxflag = 0
while True:
  if len(A) == 0:
    break
  if len(A) == 1:
    a = A.pop()
    B.appendleft(a)
    break
  if maxflag % 2 == 0:
    a = A.pop()
    b = A.pop()
  else:
    a = A.popleft()
    b = A.popleft()
  B.appendleft(a)
  B.append(b)
  maxflag += 1
ans = 0
for i in range(len(B)-1):
  ans += abs(B[i] - B [i+1])
print(ans)

Submission status: Wrong Answer

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

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

h1 = []
while 1:
    t = h.pop(-1)
    h1 = [t] + h1
    if len(h) == 0:
        break

    t = h.pop(0)
    h1.append(t)
    if len(h) == 0:
        break

    t = h.pop(-1)
    h1.append(t)
    if len(h) == 0:
        break

    t = h.pop(0)
    h1 = [t] + h1
    if len(h) == 0:
        break


h2 = []
while 1:
    t = hh.pop(0)
    h2.append(t)
    if len(hh) == 0:
        break

    t = hh.pop(-1)
    h2 = [t] + h2
    if len(hh) == 0:
        break

    t = hh.pop(-1)
    h2.append(t)
    if len(hh) == 0:
        break

    t = hh.pop(0)
    h2 = [t] + h2
    if len(hh) == 0:
        break

ans = sum([abs(i - j)  for i, j in zip(h1[1:], h1[:-1]) ])
ans1 = sum([abs(i - j) for i, j in zip(h2[1:], h2[:-1])])

if ans > ans1:
    print(ans)
else:
    print(ans1)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
from time import time
sTime = time()

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

from collections import deque
d = deque([])
A = deque(A)
for i in range(n):
    if i%2 == 0:
        x = A.popleft()
        if d:
            if abs(d[0]-x) > abs(d[-1]-x):
                d.appendleft(x)
            else:
                d.append(x)
        else:
            d.append(x)
    else:
        x = A.pop()
        if abs(d[0]-x) > abs(d[-1]-x):
            d.appendleft(x)
        else:
            d.append(x)
d = list(d)
ans = 0
for i in range(n-1):
    ans += abs(d[i+1]-d[i])

import random
max_ = ans
while True:
    tt = (time() - sTime) / 1.8
    if tt >= 1:
        print(max_)
        break
    i, j = random.sample(range(n), 2)
    if i > j:
        i, j = j, i
    if i == 0:
        ans -= abs(d[i+1]-d[i])
        ans += abs(d[i+1]-d[j])
    else:
        ans -= abs(d[i+1]-d[i])+abs(d[i-1]-d[i])
        ans += abs(d[i+1]-d[j])+abs(d[i-1]-d[j])
    if j == n-1:
        ans -= abs(d[j-1]-d[j])
        ans += abs(d[j-1]-d[i])
    else:
        ans -= abs(d[j+1]-d[j])+abs(d[j-1]-d[j])
        ans += abs(d[j+1]-d[i])+abs(d[j-1]-d[i])
    if ans > max_:
        max_ = ans
    #d[i], d[j] = d[j], d[i]

Submission status: Wrong Answer

Solution code:
from time import time
sTime = time()

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

from collections import deque
d = deque([])
A = deque(A)
for i in range(n):
    if i%2 == 0:
        x = A.popleft()
        if d:
            if abs(d[0]-x) > abs(d[-1]-x):
                d.appendleft(x)
            else:
                d.append(x)
        else:
            d.append(x)
    else:
        x = A.pop()
        if abs(d[0]-x) > abs(d[-1]-x):
            d.appendleft(x)
        else:
            d.append(x)
d = list(d)
ans = 0
for i in range(n-1):
    ans += abs(d[i+1]-d[i])

import random
max_ = ans
while True:
    tt = (time() - sTime) / 1.8
    if tt >= 1:
        print(max_)
        break
    i, j = random.sample(range(n), 2)
    if i > j:
        i, j = j, i
    if i == 0:
        ans -= abs(d[i+1]-d[i])
        ans += abs(d[i+1]-d[j])
    else:
        ans -= abs(d[i+1]-d[i])+abs(d[i-1]-d[i])
        ans += abs(d[i+1]-d[j])+abs(d[i-1]-d[j])
    if j == n-1:
        ans -= abs(d[j-1]-d[j])
        ans += abs(d[j-1]-d[i])
    else:
        ans -= abs(d[j+1]-d[j])+abs(d[j-1]-d[j])
        ans += abs(d[j+1]-d[i])+abs(d[j-1]-d[i])
    if ans > max_:
        max_ = ans
    d[i], d[j] = d[j], d[i]

Submission status: Wrong Answer

Solution code:
from time import time
sTime = time()

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

from collections import deque
d = deque([])
A = deque(A)
for i in range(n):
    if i%2 == 0:
        x = A.popleft()
        if d:
            if abs(d[0]-x) > abs(d[-1]-x):
                d.appendleft(x)
            else:
                d.append(x)
        else:
            d.append(x)
    else:
        x = A.pop()
        if abs(d[0]-x) > abs(d[-1]-x):
            d.appendleft(x)
        else:
            d.append(x)
d = list(d)
ans = 0
for i in range(n-1):
    ans += abs(d[i+1]-d[i])

import random
while True:
    tt = (time() - sTime) / 1.8
    if tt >= 1:
        print(ans)
        break
    i, j = random.sample(range(n), 2)
    d[i], d[j] = d[j], d[i]
    temp = 0
    for i in range(n-1):
        temp += abs(d[i+1]-d[i])
    if temp > ans:
        ans = temp

Submission status: Wrong Answer

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):
        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):
        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: Wrong Answer

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

from collections import deque
d = deque([])
A = deque(A)
for i in range(n):
    if i%2 == 0:
        x = A.popleft()
        if d:
            if abs(d[0]-x) > abs(d[-1]-x):
                d.appendleft(x)
            else:
                d.append(x)
        else:
            d.append(x)
    else:
        x = A.pop()
        if abs(d[0]-x) > abs(d[-1]-x):
            d.appendleft(x)
        else:
            d.append(x)
d = list(d)
ans = 0
for i in range(n-1):
    ans += abs(d[i+1]-d[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = int(input())
        A.append(a)
    A.sort()
    Aque = deque(A)
    Bque = deque([])
    Cque = deque([])

    a = Aque.popleft()
    Bque.append(a)
    Cque.append(a)
    flag = True; cnt = 0
    for _ in range(N-1):
        if cnt == 0:
            a = Aque.pop()
            Bque.appendleft(a)
            Cque.append(a)
            cnt += 1
        elif cnt == 1:
            a = Aque.pop()
            Bque.append(a)
            Cque.appendleft(a)
            cnt += 1
        elif cnt == 2:
            a = Aque.popleft()
            Bque.appendleft(a)
            Cque.append(a)
            cnt += 1
        else:
            a = Aque.popleft()
            Bque.append(a)
            Cque.appendleft(a)
            cnt = 0
    
    ansb = 0; ansc = 0
    for i in range(N-1):
        ansb += abs(Bque[i] - Bque[i+1])
        ansc += abs(Cque[i] - Cque[i+1])
    ans = max(ansb, ansc)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

    a = Aque.popleft()
    Bque.append(a)
    flag = True; cnt = 0
    for _ in range(N-1):
        if cnt == 0:
            Bque.appendleft(Aque.pop())
            cnt += 1
        elif cnt == 1:
            Bque.append(Aque.pop())
            cnt += 1
        elif cnt == 2:
            Bque.appendleft(Aque.popleft())
            cnt += 1
        else:
            Bque.append(Aque.popleft())
            cnt = 0
    
    ans = 0
    for i in range(N-1):
        ans += abs(Bque[i] - Bque[i+1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
A = []
for i in range(n):
    A.append(int(input()))
A = sorted(A)
min_A = A[:n//2]
max_A = list(map(lambda x: x*(-1), A[n//2:]))
ls = []
heapq.heapify(min_A)
heapq.heapify(max_A)
for _ in range(n//4):
    min_a = heapq.heappop(min_A)
    max_a = heapq.heappop(max_A)*(-1)
    ls.append(min_a)
    ls.insert(0, max_a)
    min_a = heapq.heappop(min_A)
    max_a = heapq.heappop(max_A)*(-1)
    ls.append(max_a)
    ls.insert(0, min_a)


if n%4 == 3:
    min_a = heapq.heappop(min_A)
    max_a = heapq.heappop(max_A)*(-1)
    ls.append(min_a)
    ls.insert(0, max_a)
    max_a = heapq.heappop(max_A)*(-1)
    ls.append(max_a)
    cnt = 0
    for i in range(n-1):
        cnt += abs(ls[i+1]-ls[i])
    print(cnt)
if n%4 == 2:
    min_a = heapq.heappop(min_A)
    max_a = heapq.heappop(max_A)*(-1)
    ls.append(min_a)
    ls.insert(0, max_a)
    cnt = 0
    for i in range(n-1):
        cnt += abs(ls[i+1]-ls[i])
    print(cnt)
if n%4 == 1:
    max_a = heapq.heappop(max_A)*(-1)  
    ls.append(max_a)
    cnt = 0
    for i in range(n-1):
        cnt += abs(ls[i+1]-ls[i])
    print(cnt)
if n%4 == 0:
    cnt = 0
    for i in range(n-1):
        cnt += abs(ls[i+1]-ls[i])
    print(cnt)

Submission status: Wrong Answer

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

A.sort()
n = N//2
if N%2 != 0:
    ar1,ar2 = [],[]
    ans1,ans2 = 0,0

    for i in range(n):
        ar1.append(A[-1-i])
        ar1.append(A[i])
        
    for i in range(1,len(ar1)):
        ans1 += abs(ar1[i]-ar1[i-1])
    ans1 += max(abs(ar1[0]-A[n]), abs(ar1[-1]-A[n]))
    for i in range(n):
        ar2.append(A[-1-i])
        ar2.append(A[i])
        
    for i in range(1,len(ar1)):
        ans2 += abs(ar2[i]-ar2[i-1])
    ans2 += max(abs(ar2[0]-A[n]), abs(ar2[-1]-A[n]))
    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: Wrong Answer

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

A.sort()
ar1,ar2 = [],[]
ans1,ans2 = 0,0

for i in range(N//2):
    ar1.append(A[-1-i])
    ar1.append(A[i])
    
for i in range(1,len(ar1)):
    ans1 += abs(ar1[i]-ar1[i-1])
ans1 += max(abs(ar1[0]-A[N//2]), abs(ar1[-1]-A[N//2]))
for i in range(N//2):
    ar2.append(A[-1-i])
    ar2.append(A[i])
    
for i in range(1,len(ar1)):
    ans2 += abs(ar2[i]-ar2[i-1])
ans2 += max(abs(ar2[0]-A[N//2]), abs(ar2[-1]-A[N//2]))
ans = max(ans1,ans2)
print(ans)

Submission status: Wrong Answer

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

A.sort()
ar = []
ans = 0

for i in range(N//2):
    ar.append(A[-1-i])
    ar.append(A[i])
    
for i in range(1,len(ar)):
    ans += abs(ar[i]-ar[i-1])
ans += max(abs(ar[0]-A[N//2]), abs(ar[-1]-A[N//2]))
print(ans)

Submission status: Wrong Answer

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 = []
ans = 0
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: Wrong Answer

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

A.sort()

l = 0
r = N-1
p = []
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]))

print(sum(q)-min(q))

Submission status: Wrong Answer

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

A.sort()

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

p += p
q = []

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

sum = 0
for i in range(len(q)):
    sum += q[i]
    if i >= N-1:
        sum -= q[i-N+1]
    ans = max(ans,sum)

print(ans)

Submission status: Wrong Answer

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

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])

print(ans)

Submission status: Wrong Answer

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

d = deque(sorted(A))
if N%2 == 0:
    r = deque.pop(d)
    l = deque.popleft(d)
    res = r-l
else:
    r = deque.popleft(d)
    l = r
    res = 0
while d:
    tmp = deque.pop(d)
    if abs(tmp-r) > abs(tmp-l):
        res += abs(tmp-r)
        r = tmp
    else:
        res += abs(tmp-l)
        l = tmp
    tmp = deque.popleft(d)
    if abs(tmp-r) > abs(tmp-l):
        res += abs(tmp-r)
        r = tmp
    else:
        res += abs(tmp-l)
        l = tmp
print(res)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = [int(input()) for i in range(N)]
A = sorted(A)
if N == 2:
    print(A[-1]-A[0])
    sys.exit()
ans = A[-1] + A[-2] - A[0]*2
left = A[-1]
right = A[-2]
for i in range((N-3)//2):
    hi = i // 2
    if i % 2 == 0:
        ans += left + right - A[hi+1] - A[hi+2]
        left, right = A[hi+1], A[hi+2]
    else:
        ans += A[-hi-3] + A[-hi-4] - left - right
        left, right = A[-hi-3], A[-hi-4]
if N % 2 == 0:
    mid = N//2+(N//2)%2-1
    ans += max(abs(left-A[mid]),abs(right-A[mid]))
ans2 = A[-1]*2 - A[0] - A[1]
left = A[0]
right = A[1]
for i in range((N-3)//2):
    hi = i // 2
    if i % 2 == 1:
        ans2 += left + right - A[hi+2] - A[hi+3]
        left, right = A[hi+2], A[hi+3]
    else:
        ans2 += A[-hi-2] + A[-hi-3] - left - right
        left, right = A[-hi-2], A[-hi-3]
if N % 2 == 0:
    mid = N//2+(N//2)%2-1
    ans2 += max(abs(left-A[mid]),abs(right-A[mid]))

print(max(ans, ans2))

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = [int(input()) for i in range(N)]
A = sorted(A)
if N == 2:
    print(A[-1]-A[0])
    sys.exit()
ans = A[-1] + A[-2] - A[0]*2
left = A[-1]
right = A[-2]
for i in range((N-3)//2):
    hi = i // 2
    if i % 2 == 0:
        ans += left + right - A[hi+1] - A[hi+2]
        left, right = A[hi+1], A[hi+2]
    else:
        ans += A[-hi-3] + A[-hi-4] - left - right
        left, right = A[-hi-3], A[-hi-4]
if N % 2 == 0:
    mid = N//2+(N//2)%2-1
    ans += max(abs(left-A[mid]),abs(right-A[mid]))
print(ans)

Submission status: Wrong Answer

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

ans = A[-1] + A[-2] - A[0]*2
left = A[-1]
right = A[-2]
for i in range((N-3)//2):
    hi = i // 2
    if i % 2 == 0:
        ans += left + right - A[hi+1] - A[hi+2]
        left, right = A[hi+1], A[hi+2]
    else:
        ans += A[-hi-3] + A[-hi-4] - left - right
        left, right = A[-hi-3], A[-hi-4]
if N % 2 == 0:
    ans += max(abs(left-A[N//2]),abs(right-A[N//2]))
print(ans)

Submission status: Wrong Answer

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)
    left = dq.popleft()
    right = left
    state = 0  # 0:左に大きい数字、1:右に大きい数字, 2:左に小さい数字、3: 右に小さい数字
    ans = 0
    # 中心に最小値を据えるケース
    while dq:
        if state == 0:
            n = dq.pop()
            ans += abs(left - n)
            left = n
        elif state == 1:
            n = dq.pop()
            ans += abs(right - n)
            right = n
        elif state == 2:
            n = dq.popleft()
            ans += abs(left - n)
            left = n
        else:
            n = dq.popleft()
            ans += abs(right - n)
            right = n
        state = (state + 1) % 4
    tmp = ans

    # 中心に最大値を据えるケース
    dq = deque(A)
    left = dq.popleft()
    right = left
    state = 2  # 0:左に大きい数字、1:右に大きい数字, 2:左に小さい数字、3: 右に小さい数字
    ans = 0
    while dq:
        if state == 0:
            n = dq.pop()
            ans += abs(left - n)
            left = n
        elif state == 1:
            n = dq.pop()
            ans += abs(right - n)
            right = n
        elif state == 2:
            n = dq.popleft()
            ans += abs(left - n)
            left = n
        else:
            n = dq.popleft()
            ans += abs(right - n)
            right = n
        state = (state + 1) % 4

    print(max(ans, tmp))
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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):
    d1 = deque()
    for a in A[1:]:
        d1.append(a)

    ans = 0
    l, r = A[0], A[0]
    i = 0
    while len(d1) != 0:
        if i % 2 != 0:
            x = d1.popleft()
        else:
            x = d1.pop()

        if abs(x - l) > abs(x - r):
            ans += abs(x - l)
            l = x
        else:
            ans += abs(x - r)
            r = x

        i += 1

    return ans


def func2(A):
    N = len(A)
    d1 = deque()
    for a in A[:N - 1]:
        d1.append(a)

    ans = 0
    l, r = A[-1], A[-1]
    i = 0
    while len(d1) != 0:
        if i % 2 == 0:
            x = d1.popleft()
        else:
            x = d1.pop()

        if abs(x - l) > abs(x - r):
            ans += abs(x - l)
            l = x
        else:
            ans += abs(x - r)
            r = x

        i += 1

    return ans


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

    print(max(func1(A[:]), func2(A[:])))


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 solve():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    A.sort()

    d1 = deque()
    for a in A[1:N - 1]:
        d1.append(a)

    ans = A[-1] - A[0]
    l, r = A[0], A[-1]
    i = 0
    while len(d1) != 0:
        if i % 2 == 0:
            x = d1.popleft()
        else:
            x = d1.pop()

        if abs(x - l) > abs(x - r):
            ans += abs(x - l)
            l = x
        else:
            ans += abs(x - r)
            r = x

        i += 1

    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

l.sort()


if n%2==0:
  a=l[:n//2]
  b=l[n//2:]
  a=a[::-1]
  b=b[::-1]


  ans=0
  mae=a[0]
  for i in range(len(a)):
    ans+=abs(a[i]-b[i])
    ans+=abs(a[i]-mae)
    mae=b[i]
  print(ans)
else:
  a=l[:n//2]
  b=l[n//2:]
  a=a[::-1]
  b=b[::-1]

  ans1=0
  ans2=0

  for i in range(len(a)):
    ans1+=abs(a[i]-b[i])+abs(a[i]-b[i+1])

  a=l[:n//2+1]
  b=l[n//2+1:]
  a=a[::-1]
  b=b[::-1]

  for i in range(len(b)):
    ans2+=abs(b[i]-a[i])+abs(b[i]-a[len(a)-i-1])

  print(max(ans1,ans2))

Submission status: Wrong Answer

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

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

A.sort()

half = math.floor(n/2)

max_A = max(A)

half_A = A[half]

if (n%2 == 1) & (half_A<max_A/2):
    total = sum(A[half+1:])*2 - sum(A[:half-1])*2 -A[half] - A[half-1]
elif (n % 2 == 1) & (half_A >= max_A / 2):
    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: Wrong Answer

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), c[1] - a)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

l = 1
r = n-1

que = deque()
que.append(A[0])
c = 0

while l <= r:
  if r-l==0:
    if abs(que[0]-A[r]) >= abs(que[-1]-A[r]):
      que.appendleft(A[r])
    else:
      que.append(A[r])
    r-=1
  else:    
    if c%2 == 0:    
      if abs(que[0]-A[r]) >= abs(que[-1]-A[r]):
        que.appendleft(A[r])
        que.append(A[r-1])
      else:
        que.append(A[r])
        que.appendleft(A[r-1])
      r -= 2
    else:
      if abs(que[0]-A[l]) >= abs(que[-1]-A[l]):
        que.appendleft(A[l])
        que.append(A[l+1])
      else:
        que.append(A[l])
        que.appendleft(A[l+1])
      l += 2
  c += 1  

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

Submission status: Wrong Answer

Solution code:
def T(A):
    N=len(A)

    Q=deque(A)
    c=Q.popleft()
    R=deque([c])

    for i in range((N-1)//2):
        if i%2:
            b=Q.popleft()
            c=Q.popleft()
        else:
            b=Q.pop()
            c=Q.pop()

        if abs(R[0]-b)+abs(R[-1]-c)>=abs(R[0]-c)+abs(R[-1]-b):
            l,r=b,c
        else:
            l,r=c,b

        R.appendleft(l)
        R.append(r)

    if Q:
        c=Q.pop()
        if abs(R[0]-c)>=abs(R[-1]-c):
            R.appendleft(c)
        else:
            R.append(c)

    K=0
    for i in range(N-1):
        K+=abs(R[i]-R[i+1])
    return K
#================================================
from collections import deque

N=int(input())
A=[0]*N
for i in range(N):
    A[i]=int(input())
A.sort()
B=[-a for a in A]
print(max(T(A),T(B)))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

Q=deque(sorted(A))
c=Q.popleft()
R=deque([c])

for i in range((N-1)//2):
    if i%2:
        b=Q.popleft()
        c=Q.popleft()
    else:
        b=Q.pop()
        c=Q.pop()

    if abs(R[0]-b)+abs(R[-1]-c)>=abs(R[0]-c)+abs(R[-1]-b):
        l,r=b,c
    else:
        l,r=c,b

    R.appendleft(l)
    R.append(r)

if Q:
    c=Q.pop()
    if abs(R[0]-c)>=abs(R[-1]-c):
        R.appendleft(c)
    else:
        R.append(c)

K=0
for i in range(N-1):
    K+=abs(R[i]-R[i+1])
print(K)

Submission status: Wrong Answer

Solution code:
from collections import deque
def T(A):
    N=len(A)
    Q=deque(sorted(A))
    R=deque([])

    for i in range(N):
        if i%2:
            a=Q.popleft()
        else:
            a=Q.pop()

        if i>=2:
            b,c=R[0],R[-1]
            if abs(a-b)<=abs(a-c):
                R.append(a)
            else:
                R.appendleft(a)
        else:
            R.append(a)

        assert 1
    K=0
    for i in range(N-1):
        K+=abs(R[i]-R[i+1])
    return K
#================================================
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
    A[i]=int(input())
    B[i]=-A[i]

print(max(T(A),T(B)))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

Q=deque(sorted(A))
R=deque([])

for i in range(N):
    if i%2:
        a=Q.popleft()
    else:
        a=Q.pop()

    if i>=2:
        b,c=R[0],R[-1]
        if abs(a-b)<=abs(a-c):
            R.append(a)
        else:
            R.appendleft(a)
    else:
        R.append(a)

    assert 1

K=0
for i in range(N-1):
    K+=abs(R[i]-R[i+1])
print(K)