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 sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
A.sort(reverse=True)
ans = A[0]
cnt = 1
for x in A[1:]:
    if cnt == N-1:
        break
    if cnt == N-2:
        ans += x
        cnt += 1
    else:
        ans += 2*x
        cnt += 2
print(ans)

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(1, n):
        ans += a[i // 2]

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


print(main())

Submission status: Accepted

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

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

A = sorted(A, reverse = True)

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

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
l = [A[0]]

for Ai in A[1:]:
    l.append(Ai)
    l.append(Ai)
    
print(sum(l[:N-1]))

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
s=0
c=0
s+=l[-1]
t=0
for i in range(n-2,n//2-1,-1):
    s+=l[i]*2
    #print(l[i]*2)
if (n%2):
    s-=l[n//2]
    #print(l[n//2])
print(s)

Submission status: Accepted

Solution code:
n = int(input())
alst = list(map(int, input().split()))
alst.sort(reverse = True)
ans = 0
pos = 0
cnt = 0
while cnt < n - 1:
    cnt += 1
    ans += alst[pos]
    if cnt % 2 == 1:
        pos += 1
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
que=[]
heapify(que)
ans=0
heappush(que,-A[0])
for i in range(1,N):
    p=-heappop(que)
    ans+=p
    heappush(que,-A[i])
    heappush(que,-A[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A_s = list(map(int, input().split()))
A_s = list(reversed(sorted(A_s)))
answer = 0
for i in range(N-1):
    answer += A_s[int(i+1)//2]
print (answer)

Submission status: Accepted

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

Submission status: Accepted

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

A.sort(reverse=True)
k = N // 2

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


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)


main()

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):
    ans += a[i//2]

ans -= a[0]
print(ans)

Submission status: Accepted

Solution code:
import math
import sys
from itertools import permutations
input = sys.stdin.readline

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

cur=2
ans=arr[0]
for i in range(1,N):
    if cur>=N:
        break
    ans+=arr[i]
    cur+=1

    if cur>=N:
        break
    ans+=arr[i]
    cur+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import *
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
ans = a[0]
n -= 2
i = 1
while(n > 0):
	ans += a[i]
	n -= 1
	if(n == 0):
		break
	ans += a[i]
	n -= 1
	i += 1
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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 LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    a.sort(reverse=True)
    s = a[0]
    for i in range(n-2):
        s += a[(i>>1)+1]
    print(s)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

a.sort(reverse=True)
ans=0
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()
count=1
ans=A[-1]
id=N-2
while count!=N-1:
    if count+2<=N-1:
        ans+=2*A[id]
        count+=2
        id-=1
    else:
        ans+=A[id]
        count+=1

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

ans = 0

conf_heap = []
heapq.heapify(conf_heap)
heapq.heappush(conf_heap,-1*a_list[0])

for i in range(1,N):
    ans += -1 * heapq.heappop(conf_heap)
    heapq.heappush(conf_heap,-1*a_list[i])
    heapq.heappush(conf_heap,-1*a_list[i])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = (10000 - N)%1000
    print(ans)
    return

def examB():
    T = ["AC","WA","TLE","RE"]
    N = I()
    S = [SI()for _ in range(N)]

    ans = [0]*4
    for s in S:
        for i in range(4):
            if s==T[i]:
                ans[i] += 1
                break
    for i in range(4):
        print(T[i]+" x "+str(ans[i]))
    return

def examC():
    H, W, K = LI()
    C = [[""]*W for _ in range(H)]
    for h in range(H):
        S = SI()
        for w in range(W):
            C[h][w] = S[w]
    ans = 0
    #print(C)
    for hi in range(1<<H):
        nowC = deepcopy(C)
        for h in range(H):
            if hi&(1<<h):
                for i in range(W):
                    nowC[h][i] = "R"
        for wi in range(1 << W):
            nowCC = deepcopy(nowC)
            for w in range(W):
                if wi & (1 << w):
                    for i in range(H):
                        nowCC[i][w] = "R"
            cnt = 0
            for h in range(H):
                for w in range(W):
                    if nowCC[h][w] == "#":
                        cnt += 1
            if cnt == K:
                #print(hi, wi, nowCC)
                ans += 1
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    A.sort(reverse=True)
    ans = 0
    ans += A[0]
    cur = 0
    for i in range(2,N):
        if i%2==0:
            cur += 1
        ans += A[cur]
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
6
8 7 6 5 4 3
"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N = int(input())
	A = getlist()
	A = sorted(A)
	if N % 2 == 0:
		ans = 0
		M = int(N // 2)
		for i in range(M):
			ans += A[-1 - i] * 2
		ans -= A[-1]
		print(ans)
	else:
		ans = 0
		M = int(N // 2)
		for i in range(M + 1):
			ans += A[-1 - i] * 2

		ans -= A[-1]
		ans -= A[-1 - M]
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())),reverse=True)
ans = a[0]
n -= 2
i = 1
while n>0:
    ans += min(n,2)*a[i]
    n -= 2
    i += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a 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:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n=II()
aa=LI()
aa.sort(reverse=True)
i=1
ans=aa[0]
n-=2
while n:
    ans+=aa[i]
    n-=1
    if n==0:break
    ans+=aa[i]
    n-=1
    i+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
k=0
ans=0
for i in range(N-1):
    ans+=A[k]
    if i%2==0:
        k+=1
print(ans)
'''
9
9 8
9 8 7
9 6 8 7
9 6 8 7 5
9 6 8 4 7 5
9 3 6 8 4 7 5
9 3 6 2 8 4 7 5
9 3 6 2 8 4 7 1 5
9+8+8+7+7+6+6+5
'''

Submission status: Accepted

Solution code:
from math import ceil
from collections import defaultdict as dd
import sys
input=sys.stdin.readline
#t=int(input())
#while t:
n=int(input())
l=list(map(int,input().split()))
l.sort(reverse=True)
ans=l[0]
ii=1
cou=0
for i in range(2,n):
    if(cou==2):
        ii+=1
        cou=0
    ans+=l[ii]
    cou+=1
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]
N-=2
ptr=1

while N>0:
    if N>=2:
        ans+=A[ptr]*2
        N-=2
    else:
        ans+=A[ptr]
        N-=1
    ptr+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    A.sort(reverse = True)
    ans = 0
    space = deque()
    space.append(A[0])
    for i in range(1, N):
        ans += space.popleft()
        space.append(A[i])
        space.append(A[i])
    print(ans)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import heapq

N = int(input())
*A, = map(int,input().split())
A.sort(reverse = True)
ans = 0
q = [-A[0]]
hpop = heapq.heappop
hpush = heapq.heappush
for a in A[1:]:
    ans += -hpop(q)
    hpush(q,-a)
    hpush(q,-a)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=1)
ans=0
for i in range(N-1):
    if i==0:
        ans+=A[0]
    else:
        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)
ans = A[0]
L = [0] * N
cnt = 1
for i in range(N - 2):
  ans += A[cnt]
  L[cnt] += 1
  if L[cnt] >= 2:
    cnt += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

n = readInt()
a = readInts()
a.sort(reverse=True)

ans = a[0]
n-=2

if n%2==0:
	t = n//2
	for i in range(t):
		ans+=a[i+1]*2
		#print(ans)
else:
	t = n//2
	for i in range(t):
		ans+=a[i+1]*2
	ans+=a[t+1]

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    A.sort(reverse = True)
    ans = A[0]
    if N == 2:
        print(ans)
        return
    cnt = 1
    for i in range(1,N):
        ans += 2*A[i]
        cnt += 2
        if cnt == N - 1:
            break
        elif cnt + 1 == N - 1:
            ans += A[i + 1]
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A.sort(reverse=True)

res = 0

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

print(res)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    cnt = [0]*n
    p = 0
    ans = 0
    for _ in range(1, n):
        ans += a[p]
        cnt[p] += 1
        if p == 0 and 1 <= cnt[p]:
            p += 1
        elif 0 < p and 2 <= cnt[p]:
            p += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A =  sorted([int(i) for i in input().split()],reverse=True)

ans = 0
for i, a in enumerate(A):
    if i == 0:
        continue
    else:
        ans += A[i//2]
    #print(i,ans)
print(ans)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
hq = [-a[0]]
ans = 0
for i in range(1, n):
    ans -= heapq.heappop(hq)
    heapq.heappush(hq, -a[i])
    heapq.heappush(hq, -a[i])
print(ans)

Submission status: Accepted

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

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

ind=0
ANS=0
for i in range(N-1):
    ANS+=A[ind]
    if i%2==0:
        ind+=1
print(ANS)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    A.sort(reverse=True)
    cnt=[2]*N
    cnt[0]-=1
    now=0
    ans=0
    for i in range(N-1):
        if cnt[now]!=0:
            ans+=A[now]
            cnt[now]-=1
        else:
            now+=1
            ans+=A[now]
            cnt[now]-=1
    print(ans)
            

main()

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
B = []
for a in A[1:]:
    B.append(a)
    B.append(a)


ans = 0
ans += A[0]
ans += sum(B[:N - 2])
print(ans)

Submission status: Accepted

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

ans = a[0]
m = n - 2
for i in range(1, n):
    if m > 1:
        ans += a[i] * 2
        m -= 2
    elif m == 1:
        ans += a[i]
        m -= 1
    else:
        break

    if m == 0:
        break

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    N = INT()
    A = LIST()
    A.sort(reverse=True)

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A.sort()
ans = A.pop()

cnt = N - 2
f = 0
while cnt:
    cnt -= 1
    ans += A[-1]
    if f & 1:
        f = 0
        A.pop()
    else:
        f ^= 1

print(ans)

Submission status: Accepted

Solution code:
from math import ceil
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
c = 0
for i in range((N+1)//2):
    c += A[i]*2
print(c - A[0] - A[(N-1)//2]*((N)&1))

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
import heapq
C=[]
heapq.heappush(C,-A[0])
ans=0
for i in range(1,n):
  cur=-heapq.heappop(C)
  ans+=cur
  heapq.heappush(C,-A[i])
  heapq.heappush(C,-A[i])
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-1):
    ans += a[(i+1)//2]

print(ans)

Submission status: Accepted

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,heapq
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################

def solve():
    n = inp()
    a = inlt()
    a.sort()
    q = (sum(a[n // 2:]) * 2) - max(a)
    if n % 2 != 0:
        q = q - a[n // 2]
    print(q)
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    b = [[0] * len(a) for i in range(len(a))]
    for i in range(len(a)): 
        for j in range(len(a)): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
a = na()
a = a + a
a.sort(reverse=True)
print(sum(a[1:n]))

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort(reverse=True)
    ans = a[0]
    cou = n-2
    for i in a[1::]:
        if cou == 0:
            break
        elif cou == 1:
            ans += i
            break
        else:
            ans += 2*i
            cou -= 2
    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

n, *aaa = map(int, sys.stdin.buffer.read().split())
aaa.sort(reverse=True)
ans = 0
for i in range(n - 1):
    ans += aaa[(i + 1) // 2]

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
out = 0
i = 0
t = 1
cnt = 1
while cnt<=N-1:
    if t==1:
        out += A[i]
        t *= -1
        i+=1
    elif t==-1:
        out += A[i]
        t*=-1
    cnt+=1
print(out)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

comfort = As[0]
for i in range(1, N-1):
    comfort += As[(i+1)//2]

print(comfort)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline

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

    pq = []
    heappush(pq, -A[0])
    ans = 0
    for a in A[1:]:
        b = -heappop(pq)
        ans += b
        heappush(pq, -a)
        heappush(pq, -a)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
t = N - 2
res = a[0]
for x in a[1: ]:
  if t == 0: break
  if t >= 2:
    res += x * 2
    t -= 2
  else:
    res += x
    t -= 1
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
A.sort(reverse=True)
ans = 0
count = 0
i = 0
while count < N:
    ans += A[i]
    count += 1
    if count % 2 == 0:
        i += 1

ans -= A[0]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    q = deque([(A[0], 1)])

    ans = 0
    for i in range(1, N):
        a = A[i]

        b, c = q.popleft()
        ans += b

        if c == 0:
            q.appendleft((b, 1))

        q.append((a, 0))

    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=1)
ans = 0 + a[0]
for i in range(n-2):
    ans += a[i//2+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(1, n):
    ans += a[i // 2]
print(ans)

Submission status: Accepted

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

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):
  x = int(i / 2)
  ans += A[x]
  #print(x, ans)
print(ans)

Submission status: Accepted

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

A.sort(reverse = True)

ans = 0
can = 1
last = 0
for i in range(n-1):
    ans += A[last]
    can -= 1
    if can == 0:
        can = 2
        last += 1
print(ans)

Submission status: Accepted

Solution code:

N = int(input())

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

A.sort()
A.reverse()

ans = 0

for i in range(N-1):

    if i == 0:
        ans += A[0]
    else:
        ans += A[(i+1)//2]

print (ans)

Submission status: Accepted

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

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)