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:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
ans = A[0]
n = N - 2
for i in range(1, n // 2 + 1):
    ans += A[i] * 2

if n % 2 == 1:
    ans += A[n // 2 + 1]

print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
a.sort(reverse=True)
sm = 0
for i in range(1,n):
    sm += a[i//2]
print(sm)

Submission status: Accepted

Solution code:
n = int(input())
A = list(int(x) for x in input().split())
A.sort(reverse=True)
if n == 2:
    print(A[0])
    exit()

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

N, *A = map(int, read().split())

A.sort(reverse=True)

deq = deque([A[0]])
ans = 0
for x in A[1:]:
    ans += deq.popleft()
    deq.append(x)
    deq.append(x)

print(ans)

Submission status: Accepted

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

a.sort(reverse=True)
ans = a[0]
cnt = n - 2
i = 1
while cnt:
    use = min(2, cnt)
    ans += a[i] * use
    cnt -= use
    i += 1

print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  l.sort(reverse=True)

  ans=l[0]
  cnt=2
  for i in range(1,n):
    for j in range(2):
      cnt+=1

      if cnt>n:
        return ans

      ans+=l[i]

# main()
print(main())

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

res = a[0]
cnt = 0
i = 1
for _ in range(n-2):
    res += a[i]
    cnt += 1
    if cnt == 2:
        i += 1
        cnt = 0
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = []
l = 0
cnt = 0
for i, a in enumerate(A):
    if l != 0:
        j = l // 2
        cnt += B[j]
    B.append(a)
    l += 1
print(cnt)

Submission status: Accepted

Solution code:
#!python3

from heapq import heappop, heappush

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()


def main():
    A.sort(reverse=True)
    hq = [-A[0]]
    ans = 0
    for a in A[1:]:
        ans -= heappop(hq)
        heappush(hq, -a)
        heappush(hq, -a)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
from collections import deque

N = ii()
A = sorted(li(), reverse=True)

l = deque([A[1], A[1]])

ans = A[0]
for num in A[2:]:
    #print(l)
    ans += l.popleft()
    l.append(num)
    l.append(num)

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]
for i in range(N - 2):
    ans+=A[(i+2)//2]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
a = [int(item) for item in input().split()]
a.sort()

first = a.pop() 
second = a.pop()
score = first
places = deque((second, second))

while a:
    v = a.pop()
    score += places.pop()
    places.appendleft(v)
    places.appendleft(v)
print(score)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()
a.sort(reverse = True)

ans = a[0]
co = 2
whe = 1
while co <= n:
	if n-co >= 2:
		ans += a[whe] * 2
		whe += 1
		co += 2
	elif n-co == 1:
		ans += a[whe]
		co += 1
		break
	else:
		break
print(ans)

Submission status: Accepted

Solution code:
from heapq import *

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

r = 0
Q = [-A[0]]
for v in A[1:]:
	c = -heappop(Q)
	r += c
	heappush(Q, -v)
	heappush(Q, -v)

print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N = iIn()
A = iInLH()

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 = [int(_n) for _n in input().split()]
A.sort(reverse=True)
# print(A)
N -= 2
i = 1
res = A[0]
while N  > 0:
    if N >= 2:
        N -= 2
        res += A[i]*2
        i+=1
    else:
        N -= 1
        res += A[i]
print(res)

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())
a=list(map(int,input().split()))
a.sort(reverse=True)
if n%2==0:
    print(a[0]+2*sum(a[1:n//2]))
else:
    temp=n//2+1  
    print(a[0]+2*sum(a[1:temp-1])+a[temp-1])

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
ans = 0
for i in range(n - 1):
  ans += a[(i + 1) // 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(1,N,1):
    B.append(A[i])
    B.append(A[i])
print(sum(B[0:N-1]))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    hq = [(-A[-1], -A[-1])]
    A.pop()

    ans = 0
    while A:
        a = A.pop()
        p, q = heappop(hq)
        p, q = -p, -q
        ans += p
        if a < p:
            heappush(hq, (-a, -p))
        else:
            heappush(hq, (-p, -a))
        if a < q:
            heappush(hq, (-a, -q))
        else:
            heappush(hq, (-q, -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)
if n % 2 == 0:
    num = n // 2
    ans = sum(a[:num]) + sum(a[1:num])
else:
    num = n // 2
    ans = sum(a[:num]) + sum(a[1:num + 1])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(j)for j in input().split()]
a.sort(reverse=True)
ans=a[0]
j=1
for i in range(n-2):
    ans+=a[j]
    if i%2:
        j+=1
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-1):
    ans += A[(i + 1) // 2]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

a.sort(reverse=True)

from collections import deque
deq = deque([a[1], a[1]])

ans = a[0]

for i in range(2,n):
    ans += deq.popleft()
    deq.append(a[i])
    deq.append(a[i])

print(ans)

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()

A.sort(reverse=True)
ans=A[0]
m=n-2
i=1
while m>0:
    a=A[i]
    ans+=a
    m-=1
    if m>0:
        ans+=a
        m-=1
    i+=1
print(ans)

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    A = sorted(A, reverse=True)
    return sum(A[i//2] for i in range(1, N))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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]"
    print(solve(N, A))

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

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
#

import sys
from math import ceil
input=sys.stdin.readline

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

Submission status: Accepted

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

ans = a[0]
j = 1
cnt = 0
for i in range(n - 2):
    ans += a[j]
    
    if cnt == 1:
        cnt = 0
        j += 1
    else:
        cnt += 1
        
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ct = 0
j=n-1
a=0
for i in range(n-1):
  if((j==n-1 and ct==1) or (ct==2)):
    j-=1
    ct=0
  a+=l[j]
  ct+=1
print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=0
import heapq
hq=[]
for i in range(N):
    if i==0:
        heapq.heappush(hq,-A[i])
        continue
    else:
        tmp=heapq.heappop(hq)*-1
        ans+=tmp
        heapq.heappush(hq,-A[i])
        heapq.heappush(hq,-A[i])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
if(N%2==1):
  ans = A[0]
  for i in range(1, (N-1)//2):
    ans += A[i] * 2
  ans += A[N//2]
  print(ans)
else:
  ans = A[0]
  for i in range(1, (N+1)//2):
    ans += A[i] * 2
  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:
from heapq import heappush, heapify, heappop
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=1)
h = [-a[0]]
heapify(h)
ans = 0
for i in range(1, n):
    ans -= heappop(h)
    heappush(h, -a[i])
    heappush(h, -a[i])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import deque
space=deque([a.pop()])
ans=0
while a:
  ans+=space.popleft()
  tmp=a.pop()
  space.append(tmp)
  space.append(tmp)
print(ans)

Submission status: Accepted

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

A.sort(reverse=True)
result = 0
for i in range(N - 1):
    result += A[(i + 1) // 2]
print(result)

Submission status: Accepted

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

A.sort(reverse=True)

ans = A[0]
N -= 2

n = N // 2
ans += 2 * sum(A[1: n + 1])
if N % 2 == 1:
    ans += A[n + 1]

print (ans)

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a.sort(reverse=True)
ans = 0
for i in range(n-1):
    ans += a[(i+1)//2]
    # print(ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def doubling_LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.depth=[None]*self.node_size
            self.depth=self.bfs(0,func=lambda pr,prv,nxt,dist:prv+1)
            self.par=self.bfs(0,func=lambda pr,prv,nxt,dist:pr)
            self.db=[self.par]
            for i in range(self.node_size.bit_length()):
                #show(self.db)
                self.db+=[[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
            self.LCA_init_stat=True
        dx=self.depth[x]
        dy=self.depth[y]
        if dx>dy:
            dx,dy=dy,dx
        c=self.node_size.bit_length()
        while c>0:
            if dx+c<=dy:
                x=self.db[c][x]
                dx+=1<<c
            c>>=1
        
        if x==y:
            return x
        
        c=self.node_size.bit_length()
        while c>0:
            if self.db[c][x]!=self.db[c][y]:
                x=self.db[c][x]
                y=self.db[c][y]
            c>>=1
        
        return self.par[x]
        
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)
 
    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos

    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True

ans=0

#h,w,K=LI()
n=I()
a=LI()
a=sorted(a)
ans=a.pop()
for i in range(n-2):
    if i%2==0:
        c=a.pop()
        ans+=c
    else:
        ans+=c

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(n // 2):
    ans += A[i] * 2
if n % 2 == 1:
    ans += A[i + 1]
ans -= A[0]
print(ans)

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 += 2*sum(a[1:n//2])
else:
    ans += 2*sum(a[1:(n-1)//2])
    ans += a[(n-1)//2]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import heapq

N = ri()
A = rl()

A.sort()

heap = []
a = A.pop()
heapq.heappush(heap, (-a, a, a))

ans = 0
while A:
	a = A.pop()
	b, l, r = heapq.heappop(heap)
	b = -b
	ans += b
	heapq.heappush(heap, (-min(a, l), l, a))
	heapq.heappush(heap, (-min(a, r), a, r))
print(ans)