Problem:


Score: 400 points

Problem Statement

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 1

4
2 2 1 3

Sample Output 1

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.

Sample Input 2

7
1 1 1 1 1 1 1

Sample Output 2

6



Sample input:
4
2 2 1 3


Sample output:
7

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = list(map(int, input().split()))

A_sorted = sorted(A,reverse = True)

circle = []
heapq.heappush(circle, -A_sorted[1])
heapq.heappush(circle, -A_sorted[1])
answer = A_sorted[0]

for i in range(2,N):
    target = A_sorted[i]
    popped = heapq.heappop(circle)
    answer -= popped
    heapq.heappush(circle, -target)
    heapq.heappush(circle, -target)

print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
A = [a[0]]
for i in range(1,N):
    A.append(a[i])
    A.append(a[i])
print(sum(A[:N-1]))

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
l = sorted(l, reverse=True)

ans = l[0]
num = 1

if len(l) == 2:
  print(ans)
else:
  for i in range(1, n):
    ans += l[i]
    num += 1
    if num == n-1:
      break
    ans += l[i]
    num += 1
    if num == n-1:
      break
  print(ans)

Submission status: Accepted

Solution code:


(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A, reverse=True)

n1 = 1 + ((N - 2) // 2)
n2 = N - n1

print(sum(A[:n1]) + sum(A[1:n2]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
list.sort(a, reverse=True)

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

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
#print(sum(A)-min(A))

A.sort(reverse=True)
ans=A[0]

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

print(ans)

Submission status: Accepted

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


def log(*args):
    print(*args, file=sys.stderr)


def main():
    n = int(input())
    a = map(int, input().rstrip().split())
    ans = 0
    candidates = collections.deque()
    for v in sorted(a, reverse=True):
        if not candidates:
            candidates.appendleft(v)
            continue
        if candidates[-1] > v:
            v2 = candidates.pop()
            ans += v2
            candidates.appendleft(v)
            candidates.appendleft(v)
        else:
            candidates.appendleft(v)
            ans += v
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse = True)
#print(A)
ans = A[0]
Q = [(-A[1],-A[0]),(-A[1],-A[0])] #一つ目が大きいほうへ入れる
heapify(Q)
for i in range(2,N):
  nxt = A[i]
  s,t = heappop(Q)
  s *= -1; t*= -1 #正に戻す
  #print(s,ans)
  ans += s
  heappush(Q,(-nxt,-s))
  heappush(Q,(-nxt,-t))
  #print(Q)
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = list(map(int, input().split()))
    s.sort(reverse=True)
    res = 0
    for i in range(1, n):
        res += s[i // 2]
    print(res)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N = in_n()
    A = sorted(in_nl(), reverse=True)

    ans = A[0]
    num = 1
    i = 1
    while True:
        if num < N - 1:
            ans += A[i]
            num += 1
        if num < N - 1:
            ans += A[i]
            num += 1
        if num < N - 1:
            i += 1
        else:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(sorted(map(int, input().split()))[::-1])
ans = 0

for i in range(N-1):
  ans += A[math.ceil(i/2)]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int , input().split()))
ans = 0

#a.sort(reverse=True)
import collections
cnt = collections.Counter(a)
for i, ci in cnt.items():
    cnt[i] = ci * 2

cnt[max(a)] -= 1
n -= 1
#print(cnt)

keys = list(cnt.keys())
keys.sort(reverse=True)
for i in keys:
    if n == 0:
        break
    ans += i * min(n, cnt[i])
    n -= min(n, cnt[i])
    #print(i, n, ans)

print(ans)

Submission status: Accepted

Solution code:
# itne me hi thakk gaye
n = int(input())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
cnt = 1
ans = arr[0]
for i in range(1, n-1):
    if cnt == n-1:
        break
    if cnt == n-2:
        ans += arr[i]
        cnt += 1
    else:
        ans += 2*arr[i]
        cnt += 2
print(ans)

Submission status: Accepted

Solution code:
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])]))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=0
a=0
b=0
c=0
for i in range(1,N):
  if i==1:
    ans+=A[c]
    c+=1
    continue
  if b==0:
    ans+=A[c]
    b+=1
  else:
    ans+=A[c]
    c+=1
    b=0
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

sum_idx = -(-N // 2)-1
if N % 2 == 0:
    print(sum(A[0:sum_idx+1]) + sum(A[1:sum_idx+1]))
else:
    print(sum(A[0:sum_idx+1]) + sum(A[1:sum_idx]))

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))

As.sort(reverse=True)
rlt = As[0]

if N == 2:
  print(rlt)
  exit()

n = N // 2
if N % 2 == 1:
  for i in range(1,n):
    rlt += 2*As[i]
  rlt += As[n]
else:
  for i in range(1,n):
    rlt += 2*As[i]
  
print(rlt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
comf = a[0]
counter = n-2
for i in range(1,n):
  if counter>1:
    comf += 2*a[i]
    counter -= 2
  elif counter == 1:
    comf += a[i]
    counter -= 1
  else:
    break
print(comf)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N=II()
AS=LI()
AS.sort(reverse=True)
# print(AS)

i, j = AS[0], AS[1]
HQ=[]
heapq.heappush(HQ, (-i, -j))
heapq.heappush(HQ, (-i, -j))
# print(HQ)
res = AS[0]
for n in range(2, len(AS)):
    k = AS[n]
    i, j = heapq.heappop(HQ)
    i *= -1
    j *= -1
    res += min(i, j)
    heapq.heappush(HQ, (-k, -i))
    heapq.heappush(HQ, (-k, -j))
    # print("i: {} j: {} k:{} res:{}".format(i,j,k,res))
    # print(HQ)

print(res)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
result = 0
count = 1
while count != n:
    result += A[count // 2]
    count += 1

print(result)

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

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

def main():
    n = int(input())
    a = readInt()
    a.sort(reverse=True)
    m = {}
    order = []
    for i in range(n):
        if a[i] in m.keys():
            m[a[i]] += 1
        else:
            m[a[i]] = 1
            order.append(a[i])
    count = m[a[0]]
    num = 0
    ans = 0
    for i in range(1,n):
        if i>count*2-1:
            num += 1
            count += m[order[num]]
        ans += order[num]
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N=int(input())
alist=list(map(int,input().split()))

alist.sort(reverse=True)
answer=0
hq=[]
heapq.heappush(hq,-alist[0])
for a in alist[1:]:
  r=heapq.heappop(hq)
  answer+=-r
  heapq.heappush(hq,-a)
  heapq.heappush(hq,-a)
  
print(answer)

Submission status: Accepted

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

    #隙間には2個入る
    res = a[0]
    tmp = a[1]
    k = 1
    cnt = 0
    for i in range(2,n):
        res += tmp
        cnt+=1
        if(cnt == 2):
            k+=1
            tmp = a[k]
            cnt = 0
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import time
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()
a.sort(reverse=True)

ans = a[0]
i = 1
cnt = 2
while True:
  if cnt == N:
    break
  ans += a[i]
  cnt += 1
  if cnt == N:
    break
  ans += a[i]
  cnt += 1
  i += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

if N == 2:
    print(A[0])
    exit()
elif N == 3:
    print(A[0] + A[1])
    exit()

ans = A[0]
N -= 2

for i in range(1, N):
    if N == 0:
        break
    a = A[i]
    c = min(2, N)
    ans += a * c
    N -= c

print(ans)


"""
if N == 2:
    print(A[0])
    exit()
elif N == 3:
    print(A[0] + A[1])
    exit()

ans = sum(A[:-2]) + A[1]
print(ans)
"""

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
A = np.sort(A)[::-1]

div, mod = divmod(N, 2)

print(2 * np.sum(A[:div]) + (A[div] if mod==1 else 0) - A[0])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse = True)
ans = A[0]
cnt = 2
for i in range(1, N):
    for j in range(2):
        cnt += 1
        if cnt > N: break
        ans += A[i]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)

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

Submission status: Accepted

Solution code:
n = input()
t = int(n)
num = t-2
list = input().rstrip().split(" ")
target = []
for i in list:
    target.append(int(i))
target.sort()
target.reverse()
ans = target[0]
i = 1
k = 0
while num > 0:
    ans += target[i]
    k += 1
    num -=1
    if k == 2:
        i += 1
        k = 0
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
a.sort(reverse=True)

k = 1
index = 0
ans = 0
for i in range(n-1):
  k -= 1
  ans += a[index]
  if k == 0:
    index += 1
    k = 2

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
As = sorted(A, reverse=True)
ct = 0
if (N-1)%2 == 0:
    n = (N-2) // 2
    for i in range(n+2):
        if i == 0:
            ct += As[i]
        elif i == n+1:
            ct += As[i]
        else:
            ct +=2*As[i]
elif (N-1)%2 == 1:
    n = (N-2) // 2
    for i in range(n+1):
        if i == 0:
            ct += As[i]
        else:
            ct += 2*As[i]
print(ct)

Submission status: Accepted

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


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A):
    A.sort(reverse=True)
    ans = 0
    for k in range(1, N):
        parent = k // 2
        ans += A[parent]
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import heapq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    A = NLI()
    A = [a * (-1) for a in A]
    A.sort()
    C = []
    heapq.heapify(C)
    ans = 0
    for i, a in enumerate(A):
        if i == 0:
            heapq.heappush(C, a)
            continue

        ans -= heapq.heappop(C)
        heapq.heappush(C, a)
        heapq.heappush(C, a)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

s = 0
for i in range(1, n):
    s += a[int(i/2)]
    
print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
alist = list(map(int, input().split(" ")))

alist.sort(reverse=True)

if n%2 == 0:
  result = alist[0] + 2*sum(alist[1:int(n/2)])
  print(result)
elif n%2 == 1:
  result = alist[0] + 2*sum(alist[1:int(n//2)]) + alist[n//2]
  print(result)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort(reverse=True)
s=l[0]
n-=2
for i in range(1,n):
	if n>1:
		s+=l[i]*2
		n-=2
	elif n==1:
		s+=l[i]
		n-=1
	else:
		break
print(s)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))

arr.sort(reverse=True)

if n % 2 == 0:
    print(arr[0] + sum(arr[1:1 + (n - 2) // 2]) * 2)
else:
    print(arr[0] + sum(arr[1:1 + (n - 2) // 2]) * 2 + arr[1 + (n - 2) // 2])

Submission status: Accepted

Solution code:
N = int(input())

Alist = list(map(int, input().split()))

Alist.sort()
Alist = Alist[::-1]

if N%2==0:
    n = int((N-2)/2 + 1)
    ans = 2 * sum(Alist[:n]) - Alist[0]
    print(ans)

else:
    n = int((N-1)/2 + 1)
    ans = 2 * sum(Alist[:n]) - Alist[0] - Alist[n-1]
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = A[0]
cur = 1
count = 1
while True:
    if count <= N - 3:
        ans += A[cur] * 2
        count += 2
        cur += 1
    elif count == N - 2:
        ans += A[cur]
        count += 1
    elif count == N - 1:
        break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
As = list(map(int, input().split()))
As.sort(reverse = True)
ans = 0
if len(As) >=2:
    for n in range(1, N):
        m = math.floor(n/2)
        ans += As[m]
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
ans = [0]*(n-1)
ans[0] = a[0]

for i in range(2,n):
    p = i//2
    ans[i-1] = a[p]

print(sum(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
import heapq
def resolve():
    N,=pin()
    A=[*pin()]
    A.sort(reverse=True)

    ans=0
    h=[]
    heapq.heappush(h,0)
    for i in range(1,N):
        temp=heapq.heappop(h)
    #    print(temp)
        ans+=A[temp]
        heapq.heappush(h,i)
        heapq.heappush(h,i)
    print(ans)

#%%submit!
resolve()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = LI()

A.sort(reverse=True)
p = 0
c = 1
ans = 0
for i in range(1,N):
    ans += A[p]
    if c == 1:
        c = 0
        p += 1
    else:
        c = 1

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))[::-1]

ans = A[0]
if (N-2)%2==0:
    for i in range((N-2)//2):
        ans+=A[i+1]*2
else:
    for i in range((N-2)//2):
        ans+=A[i+1]*2
    ans+=A[(N-2)//2+1]
print(ans)

Submission status: Accepted

Solution code:
from math import *
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)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)

B = [A[0]]

for i in range(N-1):
    B.append(A[i+1])
    B.append(A[i+1])

B.sort(reverse=True)

print(sum(B[:N-1]))

Submission status: Accepted

Solution code:
from collections import deque

d= deque()

N = int(input())
L = map(int,input().split())
L = sorted(list(L))[::-1]
import heapq
ans = 0
ideal = []
ans += L[0]
del L[0]
heapq.heappush(ideal, -L[0])
heapq.heappush(ideal, -L[0])
del L[0]

for x in L:
    ans += -1 * heapq.heappop(ideal)
    heapq.heappush(ideal, -x)
    heapq.heappush(ideal, -x)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = sorted(list(map(int,input().split())),reverse=True)
kokoti = 0
if N == 1:
    print(0)
elif N==2:
    print(max(S))
else:
    kokoti += max(S)
    for x in range (1,N-1):
        if x%2 == 1:
            kokoti += S[x//2 + 1]
        else:
            kokoti += S[x//2]
    print(kokoti)

Submission status: Accepted

Solution code:
n = int(input())
lst = list(map(int ,input().split()))
lst.sort(reverse = True)
ans = lst[0]

for i in range(1, n//2):
  ans += lst[i]*2
  
if n%2 == 1:
  ans += lst[n//2]
  
  
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

ans = 0

check_num = N // 2

ans += 2 * sum(A[:check_num]) - A[0]
if N & 1 == 1:
    ans += A[check_num]

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    A.sort(reverse=True)
    sm = A[0]
    dw = (N - 2) // 2
    for i in range(1, dw + 1):
        sm += A[i] * 2
    if (N - 2) % 2 == 1:
        sm += A[dw + 1]  
    print(sm)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.reverse()
b = collections.Counter(a)
c = list(b.items())
now = 0
tnp = 1
l = 0
l += c[0][1]*2-1
if (l>=n-1):
    print(c[0][0]*(n-1))
    exit()
now = l*c[0][0]
while True:
    if (l+c[tnp][1]*2>=n-1):
        print(now + (n-l-1)*c[tnp][0])
        break
    else:
        l += c[tnp][1]*2
        now += c[tnp][0]*c[tnp][1]*2
        tnp += 1

Submission status: Accepted

Solution code:
import queue
import numpy as np
n = int(input())
aa = list(map(int, input().split()))
aa.sort(reverse=True)
aa = np.array(aa, dtype=int)*-1
q = queue.PriorityQueue()
q.put(aa[0])
cnt = 0
for i in aa[1:]:
    cnt += q.get()
    q.put(i)
    q.put(i)

print(-cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)

ans = 0

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

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
#rint(sum(a[:-1]))

c=0
for i in range(n):
    if i == 0:
        c+=0
    elif i == 1:
        c+=a[0]
    else:
        c+=a[i//2]
print(c)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)

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

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)

res = 0
if N % 2 == 0:
    r = N // 2
    for i in range(r):
        res += A[i] * 2
    print(res - A[0])
else:
    r = N // 2 + 1
    for i in range(r):
        res += A[i] * 2
    print(res - A[0] - A[r - 1])

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)

ans = a[0]

tree = [a[1]]
for i, el in enumerate(a[2:]):
    tree.append(el)
    ans += tree[i//2]

print(ans)

Submission status: Accepted

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

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

n = int(input())
a = lmp()
a.sort(reverse=True)
ans = 0
u = [a[0]]
for i in range(1, n):
    u.append(a[i])
    u.append(a[i])
print(sum(u[:n-1]))

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(map(int, input().split())), reverse=True)

    res = 0
    que = deque([A[0]])
    for i in range(1, n):
        a = que.popleft()
        res += a
        que.append(A[i])
        que.append(A[i])
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import heapq

n=int(input())
a=[-int(x) for x in input().split()]

heapq.heapify(a)
ans=heapq.heappop(a)
n-=1

while True:
    n-=1
    if n==0:
        break
    temp=heapq.heappop(a)
    ans+=temp
    n-=1
    if n==0:
        break
    ans+=temp



print(-ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = list(reversed(sorted(A)))
new_A = []
for i in range(1, N//2+1):
    new_A.append(A[i])
    new_A.append(A[i])

new_A = [0] + [A[0]] + new_A

print(sum(new_A[:N]))

Submission status: Accepted

Solution code:
input()
a=list(map(int,input().split()))
a.sort(reverse=True)

import collections
count=len(a)
ans=0
c = collections.Counter(a)
for i in c.keys():
    tmp = c[i]*2
    if count<=tmp:
        ans+=i*count
        break
    else:
        ans+=i*tmp
        count-=tmp
print(ans-max(a))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))

A = sorted(A,reverse=True)
ans = 0
ans += A[0]
if n % 2 == 0:
  j = n//2
  ans += sum(A[1:j])*2
  
else:
  j = n//2
  ans += sum(A[1:j])*2
  ans += A[j]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    total = 0
    for k in range(1, len(A)):
        # print(total, k, A[k], k // 2)
        total += A[k // 2]
    print(total)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#create date: 2020-07-05 21:16

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    a = na()
    a.sort(reverse=True)
    apre = a[0]
    cnt = 1
    q = deque()
    ans = -a[0]
    f = 0
    for ai in a[1:]:
        if ai == apre:
            cnt += 1
        else:
            for i in range(cnt*2):
                q.append(apre)
            apre = ai
            cnt = 1
            f += (cnt+1)
        if f > n:
            break
    for i in range(cnt*2):
        q.append(apre)
    for i in range(n):
        ans += q.popleft()

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
n  =int(input())
a = [int(x) for x in input().split()]
a.sort(reverse=True)
ans = 0
i=0
ind = 0
while (i<n):
    if n-i == 1:
        ans+=a[ind]
        i+=1
    else:
        ans+=2*a[ind]
        i+=2
    ind+=1
    # print(ans,i)
ans-=a[0]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=sorted(list(map(int, input().split())),reverse=True)

ans=a[0]
c=1
i=1
while c<n-1:
    ans+=a[i]
    c+=1
    if c>=n-1:
        break
    else:
        ans+=a[i]
        c+=1
    i+=1
print(ans)

Submission status: Accepted

Solution code:
# import time
# t1=time.time()
def LI():return list(map(int,input().split()))
def I(): return int(input())
# from collections import deque, Counter, defaultdict
# from heapq import heappop, heappush
# from pprint import pprint
# import numpy as np
# import itertools

n=I()
a=LI()
a.sort(reverse=True)
# print(a)

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

Submission status: Accepted

Solution code:
import queue

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
q = queue.Queue()

ans = A[0]
q.put( (A[0], A[1]) )
q.put( (A[0], A[1]) )
for i in range(2, len(A)):
  t = q.get()
  ans += min(t[0], t[1])
  q.put((t[0], A[i]))
  q.put((t[1], A[i]))
  
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
a = sorted(map(int, input().split()), reverse=True)

ans, cnt = 0, deque([a[0]])
for i in a[1:]:
    ans += cnt.popleft()
    cnt.append(i)
    cnt.append(i)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
al = list(map(int, input().split()))

al = sorted(al)[::-1]

ans = al[0]

for i in range(n-2):
    ans += al[i // 2 + 1]

print(ans)

Submission status: Accepted

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

N = ri()
A = sorted(ri_(), reverse=True)
ans = sum(A[:N // 2]) * 2 - A[0]
if N % 2 == 1:
    ans += A[N // 2]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(sorted(map(int, input().split()), reverse=True))

ret = a[0]
now = 1
for i in range(1, n - 1):
    ret += a[now]
    if i % 2 == 0:
        now += 1    

print(ret)