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:
def II(): return int(input())
def LI(): return list(map(int, input().split()))
N=II()
A=LI()
A.sort(reverse=True)
start=A[0]
if N%2==0:
  mid=sum(A[1:(N+1)//2])*2
else:
  mid=sum(A[1:(N-1)//2]*2)+A[(N-1)//2]
ans=start+mid
#print(start,mid)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    N = II()
    A = LMIIS()
    A.sort(reverse=True)
    circle = [A[0]]
    from math import log2
    ans = 0
    for i in range(ceil(log2(N))):
        new_circle = []
        len_circle = len(circle)
        for j in range(min(len_circle,N-2**i)):
            new_circle.append(circle[j])
            new_circle.append(A[2**i+j])
            ans += min(circle[j],circle[(j+1)%len_circle])
        #     # dbg('score,',A[2**i+j],min(circle[j],circle[(j+1)%len_circle]))
        # dbg(A[2**i+j],circle,new_circle)
        circle = new_circle
    
    print(ans)



        



main()

Submission status: Accepted

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

A.sort(reverse=True)

a = min(A[0], A[1])
ans = A[0]
idx = 1
c = 1

while c <= N-1:
    if(c == N-1):
        break
    if(c == N-2):
        ans += a
        break
        
    ans += a*2
    c += 2

    idx += 1
    a = min(A[idx], A[idx-1])
         
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
n=read()
a=list(reads())
a.sort(reverse=True)
res=a[0]
next=[a[1],a[1]]
k=2
while(True):
  length=len(next)
  hoge=[]
  for i in range(length):
    if k>=n:
      print(res)
      exit()
    res+=next[i]
    hoge.append(a[k])
    hoge.append(a[k])
    k+=1
  next=hoge

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())),reverse=True)
A_tmp = sorted(A[1:] + A[1:],reverse=True)
ans = 0
index = 0

for i,a in enumerate(A):
    if i == 0:
        continue
    if i == 1:
        ans += A[0]
    else:
        ans += A_tmp[index]
        index += 1
print(ans)

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(2, 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)

from collections import deque
d = deque()
ans = 0

d.append(A[0])
for i in range(1,N):
    d.append(A[i])
    d.append(A[i])
    ans += d.popleft()

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n, *a = map(int, open(0).read().split())
    b = sorted(a)

    ans = b[-1]
    cnt = n - 2
    i = -1
    for _ in range(n - 2):
        i -= 1
        if cnt == 0:
            break
        if cnt == 1:
            ans += b[i]
            break
        cnt -= 2
        ans += 2 * b[i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

N = int(input().strip())
As = list(map(lambda s: -int(s), input().strip().split()))

heapq.heapify(As)

g  = 0
gs = collections.deque()

for n in range(N):

    a = - heapq.heappop(As)

    if n == 0:
        gs.append(a)    
    else:
        g += gs.popleft()
        gs.append(a)
        gs.append(a)

print(g)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Accepted

Solution code:
import heapq


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


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


def solve():
    """
    Circle

    left with [A, B] and A < B

    _ _ A B _

    _ _ B A _

    """
    N = read_int()
    A = read_ints()
    A.sort()
    A_max = A.pop()
    ranges = [(-A_max, -A_max)]
    score = 0
    while A:
        a = A.pop()
        left, right = heapq.heappop(ranges)
        score += -left
        heapq.heappush(ranges, (-a, left))
        heapq.heappush(ranges, (-a, right))
    return score


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)
a = A.pop(0)
h = []
heapq.heappush(h, (-a, (a, a)))
ans = 0
for a in A:
    score, (a1, a2) = heapq.heappop(h)
    ans += (-score)
    s1 = min(a, a1)
    s2 = min(a, a2)
    heapq.heappush(h, (-s1, (a, a1)))
    heapq.heappush(h, (-s2, (a, a2)))
print(ans)

Submission status: Accepted

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

if N >= 2:
    ans = num_list[0]
    N -= 2
    count = 1
    while N != 0:
        if N-2 >= 0:
            ans += num_list[count]*2
            count += 1
            N -= 2
        elif N-2 < 0:
            ans += num_list[count]
            break
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

A = list(map(int, input().split()))
A.sort(reverse=True)
edge = deque([(A[0], A[1]), (A[0], A[1])])

count = A[0]

for a in A[2:]:
  (l, r) = edge.popleft()
  count += r
  edge.append((l, a))
  edge.append((r, a))
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def main():
    n = int(input())
    a = list(map(int, input().split()))

    a.sort(reverse=True)
    ans = 0

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

    print(ans)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N = int(input())
A = [-int(x) for x in input().split()]
A = sorted(A)
ans = 0
I = [A[0]]
for a in A[1:]:
  ans += heappop(I)
  heappush(I, a)
  heappush(I, a)
print(-ans)

Submission status: Accepted

Solution code:
import sys
import math
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()
n=int(input())
a=get_array()
a.sort(reverse=True)
b=[a[0]]
for i in range(1,n//2):
    b.append(a[i]*2)
if n%2==0:
    print(sum(b))
else:
    print(sum(b)+a[i+1])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A, reverse = True)
ans = A[0]
A.remove(A[0])
B = []
for i in range(len(A)):
    B.append(A[i])
    B.append(A[i])

for i in range (N-2):
    ans += B[i]

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

a = np.array(list(map(int, input().split())))

a.sort()
a = a[::-1]
ans = 0
cnt = 0
flag = 0
for _ in range(n-1):
  ans += a[cnt]
  flag = 1-flag
  cnt += flag

print(ans)

Submission status: Accepted

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

if N%2==1:
  ans-=A[i]
else:
  ans=ans-(A[i]*2)

if N//2!=0:
  ans-=A[0]

print(max(ans,0))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = a[0]
small_idx = 1
small_idx_count = 0
for i in range(2, n):
    ans += a[small_idx]
    small_idx_count += 1
    if small_idx_count == 2:
        small_idx += 1
        small_idx_count = 0
    #print("small_idx is", small_idx)
    #print("small_idx_count is", small_idx_count)
print(ans)

Submission status: Accepted

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

if N == 2:
    print(A[0])

else:
    ans = A[0]
    cnt = 1
    n = N - 2

    while(1):

        ans += A[cnt]
        n -= 1
        if n == 0:  break

        ans += A[cnt]
        n -= 1
        if n == 0:  break

        cnt += 1

    print(ans)

Submission status: Accepted

Solution code:
import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
n = II()
a = LI()
a.sort(reverse=True)
ans = 0
for i in range(1,n):
	ans+=a[i-math.ceil(i/2)]
print(ans)

Submission status: Accepted

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

friend.sort(reverse=True)

ans = 0
for i in range(N):
    ans += friend[i//2]

ans -= friend[0]
print(ans)

Submission status: Accepted

Solution code:
import heapq
n = int(input())
A = sorted(map(int, input().split()), reverse=True)

ans = A[0]
conf = [-A[1]]
for i, a in enumerate(A[2:]):
    x = -heapq.heappop(conf)
    ans += x
    if i == 0:
        heapq.heappush(conf, -x)
    heapq.heappush(conf, -a)
    heapq.heappush(conf, -a)
print(ans)

Submission status: Accepted

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

A = sorted(a, reverse=True)
ans = 0

ans += A[0]
for i in range(2,len(A)):
    ans += A[i//2]
print(ans)

Submission status: Accepted

Solution code:
#from bisect import bisect_left as bl                #c++ lowerbound bl(array,element)
#from bisect import bisect_right as br               #c++ upperbound br(array,element)
#from __future__ import print_function, division    #while using python2


def modinv(n,p):
    return pow(n,p-2,p)

def main():
    #sys.stdin = open('input.txt', 'r')
    #sys.stdout = open('output.txt', 'w')

    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort(reverse=True)
    series = [a[0]]
    
    i = 1
    k = 1
    while True:
        if k == n-1:
            break
        series.append(a[i])
        k += 1
        if k == n-1:
            break
        series.append(a[i])
        k += 1
        i += 1    

    # print(series)
    print(sum(series))

#------------------ Python 2 and 3 footer by Pajenegod and c1729-----------------------------------------
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
#import numpy as np
#import functools
#import operator
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as comb_with
#from itertools import permutations as perm
#import collections as C #most_common
#import math
#import sympy

N = int(input())
#H,W,K= map(int,input().split())
A = list(map(int,input().split()))
#S = str(input())
#T = str(input())
A.sort(reverse=True)
ans=0
num=0
c=1
for i in range(N-1):
    ans+=A[num]
    #print(ans)
    c+=1
    if c==2:
        num+=1
        c=0
print(ans)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
4
2 2 1 3
'''

def solve(l):
	n = len(l)
	l.sort(reverse=True)
	ans = 0
	ans = 0
	hp = [[-l[0],-l[0]]]
	for i in range(1,n):
		curr = l[i]
		p = heappop(hp)
		minn = max(p)
		ans -= minn
		ll = [max(p),-curr]
		ll.sort(reverse=True)
		heappush(hp,ll)
		ll = [min(p),-curr]
		ll.sort(reverse=True)
		heappush(hp,ll)
	return ans
	

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

b = sorted(a)[::-1]
if N == 1:
    print(a[0])
elif N == 2:
    print(a[0])
elif N > 2 and N % 2 == 0:
    print(b[0] + sum(b[1:N // 2]) * 2)
elif N > 2 and N % 2 == 1:
    print(b[0] + sum(b[1:(N - 1) // 2]) * 2 + b[(N - 1) // 2])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


N = int(readline())
A = list(map(int, readline().rstrip().split()))
A = sorted(A, reverse=True)

M = -(-N // 2)
ans = A[0]
for m in range(1, M):
    ans += A[m] * 2

if N % 2 != 0:
    ans -= A[M - 1]

print(ans)

Submission status: Accepted

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

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

list.sort(A, reverse=True)

ans = A[0]

for i in range(2,N):
    ans += A[i//2]

print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n = I()
a = LI()
a = list(map(lambda x: -x, a))
a = sorted(a)
l = []
heapq.heapify(l)
ans = 0
heapq.heappush(l, a[0])
for elem in a[1:]:
    ans += -heapq.heappop(l)
    heapq.heappush(l, elem)
    heapq.heappush(l, elem)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for i in range(1,N):
  a = math.floor(i/2)
  ans += A[a]
    
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
a.sort(reverse=1)
print(sum(a[:0--n // 2]) * 2 - max(a) - a[n // 2] * (n % 2))

Submission status: Accepted

Solution code:
n=int(input())
aa=list(map(int,input().split()))
aa=sorted(aa,reverse=True)
ans=0
if (n-1)%2==1:
  ans+=aa[0]
  for i in range(int((n-2)/2)+1):
    if i!=0:
      ans+=(aa[i]*2)
else:
  ans+=aa[0]
  for i in range(int((n-3)/2)+1):
    if i!=0:
      ans+=(aa[i]*2)
  ans+=aa[int((n-3)/2)+1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse = True)
ans = A[0]
M = N-2
for i in range(1,N):
    if M <= 0:
        break
    ans += A[i]
    M -= 1
    if M <= 0:
        break
    ans += A[i]
    M -= 1
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = input_ints()
    A = input_int_list_in_line()

    A.sort(reverse=True)

    ans = A[0]

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

    print(ans)


def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


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


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()

Submission status: Accepted

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

A = sorted(A, reverse=True)

ans = A[0]
count = 2
index = 1
if N == 2:
  print(ans)
else:
  flag = 0
  while flag == 0:
    for i in range(2):
      ans += A[index]
      count += 1
      
      if count == N:
        flag = 1
        break
    index += 1
  print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

n, *a = map(int, open(0).read().split())
a.sort()
a = deque(a)
que = deque([])
que.append(a.pop())
c = 0
while a:
    c += que.popleft()
    nt = a.pop()
    que += [nt] * 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]
N-=2
index=1
while(N>0):
    if(N>=2):
        ans+=2*A[index]
        index+=1
        N-=2
    elif(N==1):
        ans+=A[index]
        index+=1
        N-=1
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
if N % 2 == 0: print(sum(A[:N // 2]) * 2 - A[0])
else: print(sum(A[:ceil(N / 2)]) + sum(A[:N // 2]) - A[0])

Submission status: Accepted

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

import itertools
from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x, file=sys.stderr)


def blute_solve(N, AS):
    "void()"
    buf = []

    def blute(xs, buf):
        debug("blute: xs, buf", xs, buf)
        if not xs:
            return 0
        if not buf:
            # first player score 0
            return blute(xs[1:], [xs[0]])
        # insert
        candidate = []
        for i in range(len(buf)):
            s = min(buf[i - 1], buf[i])
            newBuf = buf[:]
            newBuf.insert(0, xs[0])
            candidate.append(blute(xs[1:], newBuf) + s)
        return max(candidate)

    candidate = []
    for xs in itertools.permutations(range(N)):
        candidate.append(blute(xs, buf))
    return max(candidate)


def solve(N, AS):
    "void()"
    buf = []
    AS.sort(reverse=True)
    ret = AS[0]
    for i in range(N - 2):
        ret += AS[1 + i // 2]
    return ret


def main():
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


T1 = """
4
2 2 1 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    7
    """


T0 = """
3
3 2 1
"""


def test_T0():
    """
    >>> as_input(T0)
    >>> main()
    5
    """


T2 = """
7
1 1 1 1 1 1 1
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    6
    """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

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

a.sort(reverse=True)

ans = a[0]
cnt = 1
index = 1
while cnt < n - 1:
    ans += 2 * a[index]
    index += 1
    cnt += 2
    
if cnt == n - 1:
    print(ans)
else:
    print(ans - a[index - 1])

Submission status: Accepted

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




s = a*2
s.sort()
s.pop()
s.reverse()
ans = 0
for i in range(n-1):
    ans += s[i]

print(ans)

Submission status: Accepted

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

A.sort(reverse=True)
conf = 0
conf += sum(A[:N//2])
conf += sum(A[1:1+(N-1)//2])

print(conf)

Submission status: Accepted

Solution code:
N = int(input())
numbers = list(map(int, input().split()))
s = sorted(numbers, reverse = True)
total = 0
total += s[0]
s.pop(0)
z = N-2
if N%2 ==0:
    for i in range(N//2 -1):
        total += 2*s[i]
else:
    for i in range((N-3)//2):
        total += 2*s[i]
    total += s[(N-3)//2]
print(total)

Submission status: Accepted

Solution code:
import math
import collections
import fractions
import itertools
import functools
import operator

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    A.reverse()
    s = 0
    for i in range(1,N):
        s += A[i//2]
    print(s)

main()

Submission status: Accepted

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

a=sorted(a_ls,reverse=True)

ans=0

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

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

print(ans)


# 2darray [[0] * 4 for i in range(3)]

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import collections
from heapq import *
import json
l=[]
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
l.sort(key=lambda x:x[0],reverse=True)
ans=0
num=N-1
for i in range(len(l)):
    if i==0:
        ans=ans+l[i][0]*min(2*l[i][1]-1,num)
        num=num-min(2*l[i][1]-1,num)
    else:
        ans=ans+l[i][0]*min(2*l[i][1],num)
        num=num-min(2*l[i][1],num)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
# = str(input())
# = map(int, input().split())
A = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]

A = list(sorted(A))
count = A[-1]
if N % 2 == 0:
    for i in range(2, N//2+1):
        count += 2 * A[-i]

else:
    for i in range(2, N//2 +1):
        count += 2*A[-i]
    count += A[-(N//2+1)]

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N = int(input())
Als = inpl()

Als.sort(reverse=True)

if N %2 !=0:
    rank = int((N-1)/2)
    sm = 0
    for j in range(1,rank):
        sm += Als[j]
    print(Als[0] + sm*2 + Als[rank])
else:
    rank = int(N/2)
    sm = 0
    for j in range(1,rank):
        sm += Als[j]
    print(Als[0] + sm*2)

Submission status: Accepted

Solution code:
N = int(input())

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



A.sort()

res = A[-1]

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


for i in range(1,N):
    res += 2*A[-1-i]
    if 1 + 2*i == N-1:
        break
    if 1 + 2*i == N:
        res -= A[-1-i]
        break


print(res)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
n = int(input())

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

a.sort(reverse=True)

l = len(a) - 1
ans = a[0]
a = a[1:]
l -= 1
h = l//2
ans += sum(a[:h]) * 2
if l - h*2 > 0:
    ans += a[h]
print(ans)

Submission status: Accepted

Solution code:
import queue

N = int(input())
l = [int(x) for x in input().split()]
l.sort(reverse=True)
ans = 0
room = queue.Queue()
room.put(l[0])
for i in range(1, N):
    ans += room.get()
    room.put(l[i])
    room.put(l[i])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n = ni()
a = sorted(nl())
ans = a.pop()
i = n - 2
while i > 0:
    if i == 1:
        ans += a.pop()
        break
    else:
        i -= 2
        ans += a.pop()*2
print(ans)

Submission status: Accepted

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