AtCoder Beginner Contest 173 - Chat in a Circle

Quickly after finishing the tutorial of the online game ATChat, you have decided to visit a particular place with N-1 players who happen to be there. These N players, including you, are numbered 1 through N, and the friendliness of Player i is A_i.
The N players will arrive at the place one by one in some order. To make sure nobody gets lost, you have set the following rule: players who have already arrived there should form a circle, and a player who has just arrived there should cut into the circle somewhere.
When each player, except the first one to arrive, arrives at the place, the player gets comfort equal to the smaller of the friendliness of the clockwise adjacent player and that of the counter-clockwise adjacent player. The first player to arrive there gets the comfort of 0.
What is the maximum total comfort the N players can get by optimally choosing the order of arrivals and the positions in the circle to cut into?

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq A_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 \dots A_N

-----Output-----
Print the maximum total comfort the N players can get.

-----Sample Input-----
4
2 2 1 3

-----Sample Output-----
7

By arriving at the place in the order Player 4, 2, 1, 3, and cutting into the circle as shown in the figure, they can get the total comfort of 7.

They cannot get the total comfort greater than 7, so the answer is 7.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = a[0]
for i in range(2, n):
	ans += a[i // 2]
print(ans)


n = int(input())
A = sorted(list(map(int, input().split())))[::-1]
if n % 2 == 0:
	print(sum(A[:n // 2] * 2) - A[0])
else:
	print(sum(A[:n // 2] * 2) - A[0] + A[n // 2])


n = int(input())
a = sorted(list(map(int, input().split())))
ans = a.pop()
for i in range(n // 2 - 1):
	ans += 2 * a.pop()
if n % 2 == 1:
	ans += a.pop()
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
x = n // 2
y = n % 2
print(A[0] + sum(A[1:x]) * 2 + A[x] * y)


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
if N % 2 == 0:
	x = A[0]
	x += sum(A[1:N // 2]) * 2
	print(x)
else:
	x = A[0]
	x += sum(A[1:(N - 1) // 2]) * 2
	x += A[(N - 1) // 2]
	print(x)


def main():
	N = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	ans = A[0] + sum((A[i // 2 + 1] for i in range(N - 2)))
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
ans = 0
for i in range(1, n):
	ans += a[i // 2]
print(ans)


import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp
INF = inf
MOD = 1000000007
n = int(input())
A = [int(i) for i in input().split()]
tmp = 0
res = 0
A = sorted(A, reverse=True)
res = A[0] + 2 * sum(A[1:n // 2]) + n % 2 * A[n // 2]
print(res)


N = int(input())
A = list(map(int, input().split()))
B = []
for a in A:
	B.append(a)
	B.append(a)
B.sort()
B.pop()
ans = 0
for i in range(N - 1):
	ans += B.pop()
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
print(sum((a[(i + 1) // 2] for i in range(n - 1))))


N = int(input())
A = list(map(int, input().split())) * 2
A.sort()
print(sum(A[N:-1]))


n = int(input())
a = sorted([int(x) for x in input().split()], reverse=True)
ans = 0
for i in range(n - 1):
	ans += a[(i + 1) // 2]
print(ans)


N = int(input())
lA = list(map(int, input().split()))
lA.sort(reverse=True)
cnt = lA[0]
for a in range(2, len(lA)):
	cnt += lA[a // 2]
print(cnt)


from math import floor, log2
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
m = floor(log2(N))
print(sum((A[i // 2] for i in range(1, N))))


n = int(input())
A = tuple(sorted(map(int, input().split()), reverse=1))
z = n - 2
ans = A[0]
now = 1
while z:
	if z == 1:
		print(A[now] + ans)
		return
	else:
		z -= 2
		ans += A[now] * 2
		now += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
AA = A + A
AA.sort(reverse=True)
ans = 0
for i in range(1, N):
	ans += AA[i]
print(ans)


N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
ans = 0
for i in range(1, N):
	ans += A[i // 2]
print(ans)


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 6)
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
nn = lambda : list(stdin.readline().split())
ns = lambda : stdin.readline().rstrip()
n = ni()
a = na()
a = sorted(a)[::-1]
ans = sum(a[:(n + 1) // 2]) * 2 - a[0]
ans = ans if n % 2 == 0 else ans - a[(n + 1) // 2 - 1]
print(ans)


(n, *a) = map(int, open(0).read().split())
a.sort()
a = a[::-1]
ans = 0
for i in range(1, n):
	ans += a[i // 2]
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = A[0] + sum((2 * a for a in A[1:n // 2]))
if n % 2 == 1:
	ans += A[n // 2]
print(ans)


n = int(input())
li = list(map(int, input().split()))
li.sort(reverse=True)
ans = [li[0]] + li[1:] * 2
ans.sort(reverse=True)
print(sum(ans[:n - 1]))


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = sum(A[:N // 2]) * 2 - A[0]
if N % 2 == 1:
	ans += A[N // 2]
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
cur = 1
cnt = 0
ans = a[0]
for i in range(1, n - 1):
	ans += a[cur]
	cnt += 1
	if cnt == 2:
		cur += 1
		cnt = 0
print(ans)


def main():
	N = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	ans = a[0]
	t = N - 2
	for i in range(1, N):
		for _ in range(2):
			if t > 0:
				ans += a[i]
				t -= 1
	print(ans)

def __starting_point():
	main()
__starting_point()


N = int(input())
A = list(map(int, input().split()))
A.sort()
A = A[::-1]
ans = A[0]
for i in range(N - 2):
	ans += A[1 + i // 2]
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
(q, r) = divmod(n, 2)
print(a[0] + sum(a[1:q]) * 2 + a[q] * r)


import math
import sys
import os
from operator import mul
sys.setrecursionlimit(10 ** 7)

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

def I():
	return int(_S())

def LS():
	return list(_S().split())

def LI():
	return list(map(int, LS()))
if os.getenv('LOCAL'):
	inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0] + '.txt'
	sys.stdin = open(inputFile, 'r')
INF = float('inf')
N = I()
A = LI()
A.sort(reverse=True)
(half, isOdd) = divmod(len(A), 2)
ans = A[0]
for i in range(1, half):
	ans += 2 * A[i]
if isOdd == 1:
	ans += A[half]
print(ans)


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
score = [A[0]]
for i in range(1, N):
	for j in range(2):
		score.append(A[i])
	if len(score) >= N:
		break
print(sum(score[:N - 1]))


n = int(input())
a = sorted(list(map(int, input().split())))
s = a[:]
ans = 0
c = 0
for i in range(n - 1):
	if i == 0:
		ans += s.pop()
	elif c == 0:
		ans += s[-1]
		c += 1
	elif c == 1:
		ans += s.pop()
		c = 0
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
p = 0
ans = 0
for i in range(n):
	if i == 0:
		continue
	ans += a[p]
	if i % 2 == 1:
		p += 1
print(ans)


N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
ans = 0
index_val = int(N // 2)
ans += a[0]
for i in range(1, index_val):
	ans += 2 * a[i]
if N % 2 != 0:
	index_val = N // 2
	ans += a[index_val]
print(ans)


(n, *a) = map(int, open(0).read().split())
a.sort(reverse=True)
p = []
for i in range(n):
	p.append(a[i])
	p.append(a[i])
print(sum(p[:n]) - p[0])


n = int(input())
a = sorted(map(int, input().split()))
comfort = a[-1]
for i in range(n - 2):
	comfort += a[-2 - i // 2]
print(comfort)


import sys

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

def main():
	n = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	ans = A[0]
	for i in range(n - 2):
		ans += A[i // 2 + 1]
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
b = a[0]
for i in range(2, n):
	b += a[i // 2]
print(b)


n = int(input())
f = list(sorted(map(int, input().split()), reverse=True))
score = 0
for i in range(1, n):
	score += f[i // 2]
print(score)


(N, *As) = map(int, open(0).read().split())
As.sort()
print(As[-1] + sum((As[-2 - i // 2] for i in range(N - 2))))


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
P = A[0]
for i in range(2, N):
	P += A[i // 2]
print(P)


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
cnt = a[0]
if n % 2 == 0:
	for i in range(1, n // 2):
		cnt += a[i] * 2
else:
	for i in range(1, (n - 1) // 2):
		cnt += a[i] * 2
	cnt += a[(n - 1) // 2]
print(cnt)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
from math import floor
for i in range(1, n):
	ans += a[n - 1 - floor(i / 2)]
print(ans)


import math

def solve():
	N = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	A_half = math.ceil(N / 2)
	A_pre = A[:A_half]
	A_post = A[A_half:]
	ret = sum(A_pre)
	for i in range(len(A_post) - 1):
		ret += min(A_pre[i], A_pre[(i + 1) % A_half])
	print(ret)
solve()


M = int(input())
li = list(map(int, input().split()))
li = sorted(li * 2, reverse=True)
print(sum(li[1:M]))


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
circle = []
sum_val = 0
for idx in range(1, len(A)):
	sum_val += A[idx // 2]
print(sum_val)


N = int(input())
A = list(map(int, input().split()))
A.extend(A)
A.sort()
A.pop()
print(sum(A[-1:N - 1:-1]))


n = int(input())
a = sorted(list(map(int, input().split())))[::-1]
print(a[0] + sum(a[1:n // 2]) * 2 + sum(a[n // 2:n // 2 + n % 2]))


N = int(input())
A = list(map(int, input().split()))
A += A
A.sort(reverse=True)
print(sum(A[1:N]))


N = int(input())
(*A,) = sorted(map(int, input().split()), reverse=True)
n = N - 2
a = A[0]
i = 1
while 1 < n:
	a += A[i] * 2
	i += 1
	n -= 2
print(a + A[i] if n else a)


(n, *a) = map(int, open(0).read().split())
a.sort(reverse=True)
print(a[0] + sum(a[1:n // 2]) + sum(a[1:n - n // 2]))


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
print(sum([A[(1 + i) // 2] for i in range(N - 1)]))


N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = max(A)
for i in range(N - 2):
	ans += A[-(2 + i // 2)]
print(ans)


(n, *a) = map(int, open(0).read().split())
a = a + a
a.sort()
print(sum(a[-n:-1]))


n = int(input())
a = list(sorted(map(int, input().split())))[::-1]
ans = 0
for x in range(1, n):
	ans += a[x // 2]
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
total = 0
for i in range(n - 1):
	total += A[(i + 1) // 2]
print(total)


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = a[0]
if n == 2:
	print(ans)
elif n % 2 == 0:
	ans += sum(a[1:n // 2]) * 2
	print(ans)
else:
	ans += sum(a[1:n // 2]) * 2
	ans += a[n // 2]
	print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
a.insert(0, 0)
ans = 0
for i in range(1, n):
	ans += a[n - i // 2]
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = sum(a[n // 2:]) * 2 - a[-1]
if n % 2 != 0:
	ans -= a[n // 2]
print(ans)


n = int(input())
a = list(map(int, input().split()))
b = []
b = a + a + b
b.sort(reverse=1)
print(sum(b[2:n]) + b[0])


n = int(input())
A = sorted(list(map(int, input().split())))
ans = 0
for i in range(n - 1):
	ans += A[n - i // 2 - i % 2 - 1]
print(ans)


import heapq
n = int(input())
a = list(map(int, input().split()))
a = list([x * -1 for x in a])
heapq.heapify(a)
total = 0
total += -1 * heapq.heappop(a)
if n % 2 == 1:
	for i in range(1, n // 2 + 1):
		if i == n // 2:
			total += -1 * heapq.heappop(a)
		else:
			total += -2 * heapq.heappop(a)
	print(total)
else:
	for i in range(1, n // 2):
		total += -2 * heapq.heappop(a)
	print(total)


n = int(input())
a = [int(x) for x in input().split()]
list.sort(a, reverse=True)
ans = a[0]
ans += sum(a[1:n // 2]) * 2 + n % 2 * a[n // 2]
print(ans)


n = int(input())
a = list(map(int, input().split()))
a = a + a
a.sort(reverse=True)
a = a[1:n]
print(sum(a))


N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
conf = 0
for k in range(1, N):
	conf += A[N - 1 - k // 2]
print(conf)


N = int(input())
A = sorted(map(int, input().split()), reverse=True)
print(sum((A[i // 2] for i in range(1, N))))


n = int(input()) - 1
a = sorted(list(map(int, input().split())))
b = n // 2 + 1
ans = sum(a[-b:]) * 2 - a[-1]
if n % 2 == 0:
	print(ans - a[-b])
else:
	print(ans)


n = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
i = 1
s = A[0]
while i < n - 1:
	i += 1
	s += A[i // 2]
print(s)


from collections import deque
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
q = deque([a[0]])
ans = 0
for i in range(n - 1):
	ans += q.popleft()
	q.extend([a[i + 1], a[i + 1]])
print(ans)


N = int(input())
A = [int(i) for i in input().split()]
A = sorted(A, reverse=True)
A += A[1:]
A = sorted(A, reverse=True)
print(sum(A[:N - 1]))


n = int(input())
a = map(int, input().split())
s = sorted(a, reverse=True)
print(sum((s[i // 2] for i in range(1, n))))


N = int(input())
A = sorted(map(int, input().split()), reverse=True)
ans = sum(A[:N // 2]) + sum(A[1:-(-N // 2)])
print(ans)


from collections import deque
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
a = deque(A)
arrival = 1
ans = 0
while arrival < N:
	score = a.popleft()
	if arrival == 1:
		ans += score
		arrival += 1
	else:
		ans += score * min(2, N - arrival)
		arrival += 2
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = sorted(A + A[1:], reverse=True)
print(sum(B[:n - 1]))


m = len(bin((n := int(input())))) - 4
A = sorted([*map(int, input().split())])[::-1]
print(2 * sum(A[:(x := (2 ** m - (-n + 2 ** (-~m)) // 2))]) - A[0] - n % 2 * A[x - 1])


n = int(input())
a = list(map(int, input().split()))
a.sort()
if n % 2 == 0:
	suma = 2 * sum(a[-int(n / 2):]) - a[-1]
else:
	suma = 2 * sum(a[-int((n + 1) / 2):]) - a[-1] - a[-int((n + 1) / 2)]
print(suma)


(n, *a) = map(int, open(0).read().split())
a = sorted(a)[::-1]
print(sum(a[:n // 2]) * 2 - a[0] + a[n // 2] * (n % 2 != 0))


N = int(input())
A = sorted(map(int, input().split()), reverse=True)
if N % 2 == 1:
	print(sum(A[0:(N - 1) // 2]) + sum(A[1:(N + 1) // 2]))
else:
	print(sum(A[0:N // 2]) + sum(A[1:N // 2]))


n = int(input())
l = list(map(int, input().split()))
l = l + l
l = sorted(l, reverse=1)
print(sum(l[1:n]))


n = int(input())
l = list(map(int, input().split()))
l.sort()
sum = l[-1]
for i in range(1, n // 2):
	sum += 2 * l[-1 - i]
if n % 2 != 0:
	sum += l[n // 2]
print(sum)


n = int(input())
f = list(map(int, input().split()))
f.sort(reverse=True)
ans = 0
if n % 2 == 0:
	for i in range(n // 2):
		ans += f[i] * 2
	ans -= f[0]
else:
	for i in range(n // 2):
		ans += f[i] * 2
	ans += f[n // 2] - f[0]
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
s = a[0]
t = n // 2
s += sum(a[1:t]) * 2
if n % 2 != 0:
	s += a[t]
print(s)


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
S = 0
for i in range(N - 1):
	k = int((i + 1) / 2)
	S = S + A[k]
print(S)


N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
print(A[0] + sum(A[1:N // 2]) * 2 + A[N // 2] * (N % 2))


from collections import deque
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
q = deque()
q.append(a[0])
ans = 0
for i in range(1, n):
	b = q.popleft()
	ans += b
	b = min(b, a[i])
	for _ in range(2):
		q.append(b)
print(ans)


n = int(input())
p_list = input().split()
p_list = map(int, p_list)
p_list = sorted(p_list, reverse=True)
ans_list = []
ans = 0
for i in range(0, len(p_list)):
	if i != 0:
		ans_list.append(p_list[i])
		ans_list.append(p_list[i])
	else:
		ans_list.append(p_list[i])
for i in range(0, n - 1):
	ans += int(ans_list[i])
print(ans)


(N, *A) = map(int, open(0).read().split())
A.sort(reverse=True)
ans = A[0]
for i in range(2, N):
	ans += A[i // 2]
print(ans)


N = int(input())
A = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1, N):
	ans += A[N - 1 - i // 2]
print(ans)


N = int(input())
A = list(map(int, input().split()))
A.sort()
A.reverse()
C = 0
for i in range(1, N):
	C += A[i // 2]
print(C)


(N, *A) = map(int, open(0).read().split())
A.sort()
A = [0] + A
print(sum((A[N - k // 2] for k in range(1, N))))


n = int(input())
lst = list(map(int, input().split()))
lst.sort(reverse=True)
sm = lst[0]
sm += 2 * sum(lst[1:n // 2])
if n % 2 == 1:
	sm += lst[n // 2]
print(sm)


n = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
if n % 2 == 0:
	cnt = n // 2
	cnf = a[0] + sum(a[1:cnt]) * 2
else:
	cnt = n // 2
	cnf = a[0] + sum(a[1:cnt]) * 2 + a[cnt]
print(cnf)


N = int(input())
lsA = list(map(int, input().split()))
lsA += lsA
lsA.sort(reverse=True)
lsA.pop(0)
ans = sum(lsA[:N - 1])
print(ans)


N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
ans = 0
for i in range(1, N):
	ans += L[i // 2]
print(ans)


n = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
m = (n + 1) // 2
if n % 2 == 0:
	print(sum(A[:m - 1]) + sum(A[1:m]) + A[m - 1])
else:
	print(sum(A[:m - 1]) + sum(A[1:m]))


import heapq
N = int(input())
A = [int(x) * -1 for x in input().split()]
heapq.heapify(A)
conf = heapq.heappop(A) * -1
for i in range(N - 2):
	feel = heapq.heappop(A) * -1
	conf += feel
	if i % 2 == 0:
		heapq.heappush(A, feel * -1)
print(conf)


import math
n = int(input())
f = list(map(int, input().split()))
f.sort()
ans = 0
for i in range(1, n):
	ans += f[n - math.floor(i / 2) - 1]
print(ans)


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
ans = 0
for i in range(1, n):
	if i == 1:
		ans += a[-i]
	else:
		ans += a[-((i - 2) // 2 + 2)]
print(ans)


def main():
	N = int(input())
	friendliness = [int(a) for a in input().split(' ')]
	friendliness.sort(reverse=True)
	put = 1
	comfort = 0
	for i in range(len(friendliness)):
		if i == 0:
			put += 1
			comfort += friendliness[0]
		elif put + 2 <= len(friendliness):
			put += 2
			comfort += 2 * friendliness[i]
		else:
			comfort += (len(friendliness) - put) * friendliness[i]
			break
	print(comfort)
main()


n = int(input())
la = list(map(int, input().split())) * 2
la.sort(reverse=True)
print(sum(la[1:n]))


n = int(input())
lst = list(map(int, input().split()))
lst = sorted(lst, reverse=True)
print(sum(lst[0:n // 2]) + sum(lst[1:n - n // 2]))


N = int(input())
print(sum(sorted([int(a) for a in input().split()] * 2)[::-1][1:][:N - 1]))


n = int(input())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
c = 0
for i in range(1, n):
	c += arr[i // 2]
print(c)


N = int(input())
l = sorted(list(map(int, input().split())))
l.reverse()
s = l[0] + N % 2 * l[N // 2]
for i in range(N // 2 - 1):
	s += l[i + 1] * 2
print(s)


n = int(input())
a = list(map(int, input().split()))
a.sort()
print(sum(a[(n + 1) // 2:]) + sum(a[n // 2:n - 1]))


import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

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

def INT():
	return int(input())

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

def S_MAP():
	return map(str, input().split())

def LIST():
	return list(map(int, input().split()))

def S_LIST():
	return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
N = INT()
A = LIST()
A.sort(reverse=True)
ans = A[0]
cnt = 1
for x in A[1:]:
	if cnt == N - 1:
		break
	if cnt == N - 2:
		ans += x
		cnt += 1
	else:
		ans += 2 * x
		cnt += 2
print(ans)


def ans():
	from math import floor
	N = int(input())
	A = [0] + list(map(int, input().split()))
	A = sorted(A)
	sum_conf = 0
	for k in range(1, N):
		sum_conf += A[N - floor(k / 2)]
	print(sum_conf)

def __starting_point():
	ans()
__starting_point()


N = int(input())
A = [int(x) for x in input().split()]
ans = 0
A.sort(reverse=True)
ans += sum(A[:(N + 1) // 2 - 1])
for i in range((N + 1) // 2 - 1):
	ans += min(A[i], A[i + 1])
if N % 2 == 0:
	ans += A[N // 2 - 1]
print(ans)


N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
B = [A[0]]
for a in A[1:]:
	B += [a, a]
print(sum(B[:len(A[:-1])]))


n = int(input())
a = sorted(map(int, input().split()), reverse=True)
res = 0
res += a[0]
for i in range(2, n):
	res += a[i // 2]
print(res)


N = int(input())
a = list(map(int, input().split()))
a.sort()
ans = a[-1]
for i in range(N - 2):
	ans += a[-(i // 2) - 2]
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = 0
cnt = 0
i = 1
while cnt < n - 1:
	ans += a[(cnt + 1) // 2]
	cnt += 1
print(ans)


n = int(input())
c = list(map(int, input().split()))
c = sorted(c)
ans = 0
for i in range(1, len(c)):
	ans += c[len(c) - 1 - i // 2]
print(ans)


N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
ans = 0
cnt = 1
ans += A[0]
flag = False
for i in range(1, len(A) - 1):
	ans += A[cnt]
	if flag == False:
		flag = True
	else:
		flag = False
		cnt += 1
print(ans)


n = int(input())
A = sorted([*map(int, input().split())], reverse=True)
ans = -A[0]
for i in range(n):
	ans += A[i // 2]
print(ans)


N = int(input())
A = [int(a) for a in input().split()] * 2
A.sort()
A.reverse()
print(sum(A[1:N]))


n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
A2 = [A[0]]
for a in A[1:]:
	A2.extend([a, a])
ans = 0
for a in A2[:n - 1]:
	ans += a
print(ans)


N = int(input())
AN = list(map(int, input().split()))
AN.sort()
ans = 0
for n in range(1, N):
	ans += AN[N - 1 - n // 2]
print(ans)


N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
ans = A[0]
for i in range(N - 2):
	ans += A[(i + 2) // 2]
print(ans)


import math
N = int(input())
A = list(map(int, input().split()))
list.sort(A, reverse=True)
ans = 0
for i in range(N - 1):
	ans += A[math.ceil(i / 2)]
print(ans)


a = input()
N = int(a)
A = list(map(int, input().split()))
A.sort()
x = A[N - 1]
for i in range(1, (N - 2) // 2 + 1):
	x = x + 2 * A[N - 1 - i]
if (N - 2) % 2 == 1:
	x = x + A[N - 2 - (N - 2) // 2]
print(x)


n = int(input())
a = sorted(list(map(int, input().split())), reverse=1)
b = 0
for i in range(n - 1):
	b += a[(i + 1) // 2]
print(b)


n = int(input())
lst = list(map(int, input().split()))
lst.sort(reverse=True)
if n % 2 == 0:
	a = n // 2 - 1
	s = lst[0]
	for i in range(a):
		s += 2 * lst[i + 1]
else:
	b = (n - 1) // 2
	s = lst[0]
	for j in range(b):
		s += 2 * lst[j + 1]
	s -= lst[b]
print(s)


n = int(input())
friendry = list(map(int, input().split()))
friendry.sort()
friendry.reverse()
ans = 0
t = n - 1
for i in range(n - 1):
	lim = 2
	if i == 0:
		lim = 1
	for j in range(lim):
		if t > 0:
			ans += friendry[i]
			t -= 1
print(ans)


N = int(input())
A = sorted(list(map(int, input().split())))
ans = A[-1]
j = -2
for i in range(N - 2):
	ans += A[j]
	if i % 2 == 1:
		j -= 1
print(ans)


n = int(input())
li_a = list(map(int, input().split()))
sum_ = 0
li_a.sort()
for i in range(1, n):
	sum_ += li_a[n - 1 - i // 2]
print(sum_)


n = int(input())
a = list(map(int, input().split()))
a = sorted(a)[::-1]
s = 0
for i in range(1, n):
	s += a[i // 2]
print(s)


n = int(input())
a = sorted([int(x) for x in input().split()], reverse=True)
ans = a[0]
cnt = idx = 1
while idx < n - 1:
	for i in range(2):
		ans += a[idx]
		cnt += 1
		if cnt == n - 1:
			break
	else:
		idx += 1
		continue
	break
print(ans)


(n, *lst) = map(int, open(0).read().split())
lst.sort(reverse=1)
res = sum((lst[i // 2] for i in range(1, n)))
print(res)


n = int(input())
print(sum(sorted([int(x) for x in input().split()] * 2, reverse=True)[1:n]))


import heapq as hq
n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
p = a.pop()
q = []
hq.heappush(q, (-p, -p))
ans = 0
for _ in range(n - 1):
	p = a.pop()
	(b1, b2) = hq.heappop(q)
	ans += -b1
	hq.heappush(q, sorted((b1, -p), reverse=True))
	hq.heappush(q, sorted((b2, -p), reverse=True))
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = a[0]
num = 2
idx = 1
while num < n:
	if num + 1 == n:
		ans += a[idx]
		num += 1
	else:
		ans += a[idx] * 2
		num += 2
		idx += 1
print(ans)


import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as H
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'

def _X():
	return sys.stdin.readline().rstrip().split(' ')

def _S(ss):
	return tuple(ss) if len(ss) > 1 else ss[0]

def S():
	return _S(_X())

def Ss():
	return list(S())

def _I(ss):
	return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)

def I():
	return _I(S())

def _Is(ss):
	return list(ss) if isinstance(ss, tuple) else [ss]

def Is():
	return _Is(I())

def rec(h, w):
	return [[0] * w for i in range(h)]
n = I()
xs = Is()
xs = sorted(xs, reverse=True)
seats = [-xs[0]]
H.heapify(seats)
ans = 0
for x in xs[1:]:
	ans -= H.heappop(seats)
	H.heappush(seats, -x)
	H.heappush(seats, -x)
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
if n % 2 == 0:
	print((sum(a) - sum(a[:n // 2])) * 2 - max(a))
else:
	print((sum(a) - sum(a[:n // 2])) * 2 - max(a) - a[n // 2])


n = int(input())
A = list(map(int, input().split()))
A = A + A
ans = 0
A.sort()
A.pop()
for _ in range(n - 1):
	ans += A.pop()
print(ans)


n = int(input())
p = list(map(int, input().split()))
p.sort(reverse=True)
s = 0
for i in range(1, n):
	s += p[i // 2]
print(s)


N = int(input())
A = sorted(map(int, input().split()))
ans = 0
for k in range(1, N):
	ans += A[N - 1 - k // 2]
print(ans)


N = int(input())
An = list(map(int, input().split()))
An.sort(reverse=True)
answer = 0
t = N - 1
for (i, Ai) in enumerate(An):
	lim = 2
	if i == 0:
		lim = 1
	for j in range(lim):
		if t > 0:
			answer += Ai
		t -= 1
print(answer)


n = int(input())
(*a,) = map(int, input().split())
a.sort()
ans = a[-1]
for i in range(2, n // 2 + 1):
	ans += a[-i] * 2
if n % 2:
	ans += a[n // 2]
print(ans)


n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr, reverse=True)
ans = 0
for i in range(1, n):
	ans += arr[i // 2]
print(ans)


N = int(input())
List = list(map(int, input().split()))
List += List
List = sorted(List)[::-1]
List = List[1:N]
print(sum(List))


n = int(input())
a_list = sorted([int(x) for x in input().split()])
ans = a_list.pop()
n -= 2
while n > 0:
	a = a_list.pop()
	ans += a
	n -= 1
	if n > 0:
		ans += a
		n -= 1
print(ans)


(N, *A) = map(int, open(0).read().split())
A.sort(reverse=True)
print(2 * sum(A[:N // 2]) - A[0] + (A[N // 2] if N % 2 == 1 else 0))


n = int(input())
a = list(map(int, input().split()))
a.sort()
a.reverse()
s = a[0]
for i in a[1:n // 2]:
	s = s + i * 2
if n % 2 == 1:
	s += a[n // 2]
print(s)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque

def main():
	(n, *a) = list(map(int, read().split()))
	a.sort(reverse=True)
	a = deque(a)
	circle_joined = deque()
	next_score = a.popleft()
	r = 0
	flag = False
	while a:
		circle_joined.append(a.popleft())
		if flag:
			next_score = circle_joined.popleft()
			r += next_score
			flag = False
		else:
			r += next_score
			flag = True
	print(r)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = sorted(list(map(int, input().split())))
sum_a = 0
for i in range(n - 1):
	j = n - (i + 1) // 2
	sum_a += a[j - 1]
print(sum_a)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for k in range(1, n):
	ans += a[n - 1 - k // 2]
print(ans)


N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
N -= 1
i = 1
koko = A[0]
f = 0
while 1:
	for _ in range(2):
		N -= 1
		if N == 0:
			f = 1
			break
		koko += A[i]
	if f == 1:
		break
	i += 1
print(koko)


def chat_in_a_circle():
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	res = A.pop(-1)
	t = len(A) % 2 == 0
	a = 0
	for i in range(len(A) // 2):
		a = A.pop(-1)
		res += a * 2
	if t:
		res -= a
	print(res)
chat_in_a_circle()


N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)
print(2 * sum(A[0:~-N // 2 + 1]) - A[0] - (A[~-N // 2] if N % 2 else 0))


N = int(input())
A = [int(i) for i in input().split()]
A.sort()
S = -A[-1]
for i in range(N):
	S += A[N - i // 2 - 1]
print(S)


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = a[0]
ch = 1
for i in range(1, n):
	if ch == n - 1:
		break
	else:
		ans += a[i]
		ch += 1
	if ch == n - 1:
		break
	else:
		ans += a[i]
		ch += 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
res = 0
for i in range(1, n):
	res += l[i // 2]
print(res)


N = int(input())
a = list(map(int, input().split()))
a.sort()
arrival = 1
ans = 0
while arrival < N:
	score = a.pop()
	if arrival == 1:
		ans += score
		arrival += 1
	else:
		ans += score * min(2, N - arrival)
		arrival += 2
print(ans)


N = int(input())
ls = [int(s) for s in input().split()]
ls = sorted(ls, reverse=True)
ans = ls[0]
for i in range(2, N):
	ans += ls[i // 2]
print(ans)


N = int(input())
A = list((int(x) for x in input().split()))
A.sort()
sum = 0
for i in range(N - 1):
	k = i + 1
	sum += A[N - int(k / 2) - 1]
print(sum)


n = int(input())
a = [int(i) for i in input().split()]
sort_a = sorted(a, reverse=True)
now_list = []
next_insert = []
comfort = []
for (index, i) in enumerate(sort_a):
	if len(now_list) == 0:
		now_list += [i]
		next_insert += [1]
		comfort += [i]
	elif len(next_insert) >= n:
		break
	else:
		next_insert += [1, 1]
		comfort += [i, i]
print(sum(comfort[:n - 1]))


n = int(input())
aa = tuple(sorted(map(int, input().split()), reverse=True))
ans = 0
for i in range(1, n):
	ans += aa[i // 2]
print(ans)


N = int(input())
l = [int(x) for x in input().split()]
l.sort(reverse=True)
ans = 0
for i in range(N - 1):
	ans += l[(i + 1) // 2]
print(ans)


import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input():
	return int(input())

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

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def lcm(a, b):
	return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
	N = i_input()
	A = i_list()
	list.sort(A)
	sum = 0
	for i in range(1, N):
		sum += A[N - 1 - floor(i / 2)]
	print(sum)
	return

def __starting_point():
	main()
__starting_point()


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0
i = 0
nokori = N - 1
while nokori > 0:
	if i == 0:
		ans += A[i]
		nokori -= 1
	elif nokori == 1:
		ans += A[i]
		nokori -= 1
	else:
		ans += 2 * A[i]
		nokori -= 2
	i += 1
print(ans)