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:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
a = lr()
a.sort(reverse=True)
ans = a[0]
if (n-1)%2 == 1:
    for i in range(n//2-1):
        ans += a[i+1]*2
else:
    for i in range(n//2-1):
        ans += a[i+1]*2
    ans += a[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]
s = (N - 2) // 2
if s > 0:
    ans += sum(A[1:1 + s]) * 2
if (N - 2) % 2:
    ans += A[1 + s]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

Q = deque([0])
comfort = 0
i = 0
while Q:
    if i == n:
        break
    comfort += Q.popleft()
    if i == 0:
        Q.append(a[i])
    elif i > 0:
        Q.append(a[i])
        Q.append(a[i])
    i += 1

print(comfort)

Submission status: Accepted

Solution code:
N = int(input())
AList = list(map(int, input().split()))
sList = sorted(AList, reverse=True)
ans = sList[0]
idx = 1
for i in range(1, N-1):
  ans += sList[idx]
  if i%2 == 0:
    idx += 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans_list=[0]*(N-1)
ans_list[0]=A[0]
count=0
ind=1
for i in range(1,len(ans_list)):
    if count==2:
        count=0
        ind+=1
    ans_list[i]=A[ind]
    count+=1
print(sum(ans_list))

Submission status: Accepted

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


# print(A)

idx = []
for i in range(N + 1 // 2):
    idx.append(i)
    idx.append(i)

idx = idx[::-1]
idx = idx[1:N]
# print(idx)
ans = 0
for i in idx:
    ans += 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):
  num = i // 2
  num += 1
  if i == 0:
    ans += a[i]
  else:
    ans += a[i-num+1]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

li.sort()
if N%2==0:
  print(2*sum(li[int(-N/2):-1])+li[-1])
else:
  print(2*sum(li[-(N//2):-1])+li[-1]+li[-(N//2)-1])

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = list(map(int,input().split()))
ans = max(A)
A = [-1*item for item in A]
heapq.heapify(A)
heapq.heappop(A)
flag = 1
for i in range(N-2):
    if flag == 1:
        a = heapq.heappop(A)
        ans += -1*a
        flag = 0
    else:
        ans += -1*a
        flag = 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def solve():
    ret = 0
    A.sort(reverse=True)
    stack = deque()
    for a in A:
        if not stack:
            stack.append(a)
            continue
        ret += stack.popleft()
        stack.extend([a, a])
    print(ret)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    solve()

Submission status: Accepted

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

p = [0, l[0]]
for i in l[1:]:
    p.append(i)
    p.append(i)
    
print(sum(p[:n]))

Submission status: Accepted

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

a.sort(reverse=True)
dic = {a[0]:1}
ans = 0

for i in range(1,n):
    h = a[i]
    max_h = next(iter(dic))
    
    
    
    if h == max_h:
        dic[h] += 1
        ans += h
    
    else:
        if h in dic:
            dic[h] += 2
            dic[max_h] -= 1
            ans += max_h
        
        else:
            dic[h] = 2
            dic[max_h] -= 1
            ans += max_h
        
        if dic[max_h] == 0:
            del dic[max_h]
    
    

print(ans)

Submission status: Accepted

Solution code:

n=int(input())
x=[int(x) for x in input().split()]
x.sort(reverse=True)
ans=x[0]
c=1
for i in range(1,n):
    if c+2<n:
        c+=2
        ans+=2*x[i]
    else:break
if c<n-1:
    ans+=x[i]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
a_list.reverse()
index = 1
counter = 0
ans = a_list[0]

for i in range(2, n):
    ans += a_list[index]
    counter += 1
    if counter == 2:
        counter = 0
        index += 1

print(ans)

Submission status: Accepted

Solution code:
""" D
    https://atcoder.jp/contests/abc173/tasks/abc173_d
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

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

    sum = A[0]
    for i in range(1, N-1):
        sum += A[int((i-1)/2)+1]

    return sum

if __name__ == "__main__":
    _N = readInteger()
    _A = readIntegerSet(_N)

    print(main(_N, _A))

Submission status: Accepted

Solution code:
# Problem D - Chat in a Circle

from collections import deque

# input
N = int(input())
a_nums = list(map(int, input().split()))

# initialization
a_nums = sorted(a_nums, reverse=True)
point_list = deque([a_nums[0]])
point = 0

# count
for i in range(1, N):
    a = a_nums[i]
    point += point_list.popleft()
    point_list.append(a)
    point_list.append(a)

# output
print(point)

Submission status: Accepted

Solution code:
import heapq

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
ans=0
q=[]
heapq.heappush(q,-arr[0])
for i in range(1,n):
  ans+=-heapq.heappop(q)
  heapq.heappush(q,-arr[i])
  heapq.heappush(q,-arr[i])
print(ans)

Submission status: Accepted

Solution code:
# vim: fileencoding=utf-8


def main():
    n = int(input())
    li = list(map(int, input().split()))
    res = 0
    li = li + li
    li.sort()
    tmp = int(len(li) / 2)
    print(sum(li[-tmp:-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    count = 0
    for i in a:
        if ans ==0:
            ans+=i
            count+=1
        else:
            if count == n-2:
                ans+=i
                break
            elif count == n-3:
                ans+=i*2
                break
            else:
                ans+=i*2
                count+=2

    if n ==2:
        ans= max(a)

    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	A = A[::-1]
	ans = 0
	maxs = 0
	cnt = 0
	fst = True

	ansans = []
	pgt = queue.Queue()
	for i,val in enumerate(A):
		if i == 0:
			pgt.put(val)
		else:
			tmp = pgt.get()
			ansans.append(tmp)

			pgt.put(val)
			pgt.put(val)
	print(sum(ansans))


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import collections

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

As.sort(reverse = True)

#print(As)

circle_que = collections.deque()

circle_que.append(As[0])

ans = 0
for A in As[1:]:
    circle_que.append(A)
    circle_que.append(A)

    ans += circle_que.popleft()
    #print(ans)

print(ans)

Submission status: Accepted

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

a.sort(reverse=True)
middle = []
if (n % 2 == 0):
    middle = a[:n // 2]
    # print(middle)

    sum = sum(middle)-middle[-1]
    for i in range(n // 2-1):
        sum += middle[i + 1]
    sum += middle[-1]
else:
    middle = a[:n // 2+1]
    # print(middle)

    sum = sum(middle)-middle[-1]
    for i in range(n // 2):
        sum += middle[i+1]
print(sum)

Submission status: Accepted

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

A.sort(reverse=True)
ans = A[0]
i = 1
j = 1
while i < N-1:
    ans += A[j]
    i += 1
    if i < N-1:
        ans += A[j]
    i += 1
    j += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
m=[int(x) for x in input().split()]
m=sorted(m, reverse=True)
u=sorted(list(set(m)), reverse=True)
d={}
for i in m:
  if i in d:
    d[i]+=1
  else:
    d[i]=1
for i in d:
  if i != u[0]:
    d[i]*=2
pos=0
c=u[pos]*(d[u[pos]]-1)
posm=d[u[pos]]
for i in range(posm, len(m)):
  c+=u[pos]
  d[u[pos]]-=1
  if d[u[pos]] == 0:
    pos+=1
print(c)

Submission status: Accepted

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

a.sort()
ans = a[-1]
flg = False
ind = -2

for i in range(n - 2):
    ans += a[ind]
    if flg:
        ind -= 1
    flg = not flg

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

A.sort(reverse=True)

res = 0

res += A.pop(0)

count = 1

for i in range(N):
    for _ in range(2):
        if count < N - 1:
            res += A[i]
            count += 1

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	A = A[::-1]
	ans = 0
	maxs = 0
	cnt = 0
	fst = True

	ansans = []
	pgt = queue.Queue()
	for i,val in enumerate(A):
		if i == 0:
			pgt.put(val)
		else:
			tmp = pgt.get()
			ansans.append(tmp)

			pgt.put(val)

			if tmp == val:
				pgt.put(val)
			else:
				pgt.put(val)

	#print(ansans)
	print(sum(ansans))


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import queue

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

edge_que = queue.Queue()
edge_que.put(A_list[0])
score = 0
for i, a in enumerate(A_list[1:]):
    score += edge_que.get()
    edge_que.put(a)
    edge_que.put(a)
print(score)

Submission status: Accepted

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


a.sort(reverse=True)
cnt=0
for i in range(1,n):
    if i==1:
        cnt+=a[0]
    else:
        j = (i // 2)
        cnt += a[j]
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

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

A_sorted = sorted(A, reverse=True)
ans = 0
queue = deque([A_sorted[0]])
for a in A_sorted[1:]:
    ans += queue.popleft()
    queue.append(a)
    queue.append(a)
print(ans)

Submission status: Accepted

Solution code:
import collections

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

result = 0
max_a = A[0]
hash = {A[0]: 1}
next_max_a = collections.deque()
for i in range(1, len(A)):
    a = A[i]
    hash[max_a] -= 1
    result+=max_a

    if not(a in hash):
        hash[a] = 0
        next_max_a.append(a)
    hash[a] += 2

    if hash[max_a] <= 0:
        hash.pop(max_a)
        max_a = next_max_a.popleft()
print(result)

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop
N = int(input())
A = list(map(int, input().split()))

A.sort()
a = A.pop()
q = []
heappush(q,-a)
ans = 0
while A:
  #print(A,q)
  b = A.pop()
  a = -heappop(q)
  ans += a
  heappush(q,-b)
  heappush(q,-b)
  
print(ans)

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    lst = sorted([int(i) for i in input().split()], reverse=True)
    ans = lst[0]

    n, m = divmod(N - 2, 2)
    ans += sum(lst[1:n + 1]) * 2
    if m:
        ans += lst[n + 1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def d_chat_in_a_circle():
    N = int(input())
    A = sorted([int(i) for i in input().split()], reverse=True)

    ans = [A[0]]
    j = 1
    while True:
        ans.extend([A[j]] * 2)
        j += 1
        if len(ans) > N - 1:
            ans.pop()
            break
    if N % 2 == 0:
        ans.pop()
    return sum(ans)

print(d_chat_in_a_circle())

Submission status: Accepted

Solution code:
n=int(input())
a = list(map(int, input().split()))
b=sorted(a,reverse=True)
s=b[0]
t=2
if n==2:
  print(s)
else:
    for i in range(1,n):
        for _ in range(2):
            s+=b[i]
            t+=1
            if t==n:
                break
        else:
            continue
        break
    print(s)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=[int(_) for _ in input().split(" ")]

A.sort(reverse=True)

#print(A)

ans=0
ans+=A[0]

if len(A)%2==1:
  for i in range(1,N-1):
    ans+=A[(i+1)//2]
    #print("ans",ans)
else:
  for i in range(1,N-1):
    ans+=A[(i+1)//2]
    #print("ans",ans)

print(ans)

Submission status: Accepted

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

sorted_list = sorted(A_LIST)[::-1]

n_half = N // 2 + N % 2
pts = 0
for a in sorted_list[:n_half - 1]:
    pts += a

circle = sorted_list[1:n_half] + [sorted_list[n_half - 1]]
    
for i in range(N - n_half):
    pts += circle[i]
        
print(pts)

Submission status: Accepted

Solution code:
# import numpy as np
from collections import deque

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

A.sort(reverse=True)
# row = [A[0], A[1]]
min_list = deque([A[1], A[1]])
ans = A[0]
for i in range(2, N):
    # index = np.argmax(min_list)
    ans += min_list.popleft()
    # if index == len(min_list)-1:
    #     l, r = row[index], row[0]
    # else:
    #     l, r = row[index], row[index+1]
    # row.insert(index+1, A[i])
    min_list.append(A[i])
    min_list.append(A[i])
    # min_list.insert(index+1, A[i])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

forret = sorted(A_i)
ret = forret[-1]
for i in range(N-2):
    ret = ret + forret[-1-1-(i//2)]
print(ret)

Submission status: Accepted

Solution code:
num = int(input())
a_i = list(map(int, input().split()))
list.sort(a_i, reverse=True)
if num <= 3:
    print(sum(a_i[:num - 1]))
else:
    ans = sum(a_i[:2])
    for x in range(3, num):
        if x == 3: ans += a_i[1]
        else: ans += a_i[x // 2]
    print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=a[0]
if n==1:
    print(0)
    exit()
elif n==2:
    print(a[0])
    exit()
if n%2==0:
    ans+=2*sum(a[1:(n-2)//2+1])
   
    print(ans)
else:
    ans+=2*sum(a[1:(n-2)//2+1])+a[(n-2)//2+1]
    print(ans)

Submission status: Accepted

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

A.sort(reverse = True)

ans = A[0]
re = [A[1]]
n = 0
for num in A[2:]:
     re.append(num)
     if num < re[0]:
          n += 1
     ans += re[0]
     if n == 2:
         re.pop(0)
         n = 0

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
c = n - 2
ans = a[0]
idx = 1
while c > 0:
	ans += a[idx] * min(c,2)
	idx += 1
	c -= min(c,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:
    ts = sum(A[:n//2])
    print(ts + ts - A[0])
else:
    ts = sum(A[:n//2])
    print(ts + ts - A[0] + A[n//2])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    A = LI()
    A = sorted(A, reverse=True)
    max_a = max(A)
    ans = 0
    arr = []
    cnt = 0
    cur = 0
    v = max_a

    while cur < len(A) and v == A[cur]:
        cur += 1
        cnt += 1
        arr.append(v)
        arr.append(v)

    while cur < len(A):
        cnt = 0
        while cur < len(A) and v == A[cur]:
            cur += 1
            cnt += 1

        # print(v, cnt)
        for i in range(cnt * 2):
            arr.append(v)
        if cur < len(A):
            v = A[cur]
        if len(arr) >= 2 * N:
            break

    # print(arr)
    # print(arr[1:])
    # print(arr[1:N])
    print(sum(arr[1:N]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
S = sorted(A, reverse=True)
X = S[0]
N -= 2
i = 0
while N > 0:
    i += 1
    x = S[i]
    X += x
    if N == 1:
        break
    X += x
    N -= 2
print(X)

Submission status: Accepted

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


so = sorted(a)

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

Submission status: Accepted

Solution code:
n = int(input())
x=n
lol=[int(n) for n in input().split()]

ans = 0
lol.sort()
lol.reverse()
z=lol.copy()
ans +=lol[0]
lol.remove(max(lol))
n=n-2

if(n%2==0):
    for i in range(int(n/2)):
        ans+=(2*lol[i])
    print(ans)
else:
    for i in range(int((n-1)/2)):
        ans+=(2*lol[i])
    ans+=(z[int(x/2)])
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
d = deque()
a = [int(x) for x in input().split()]
a = sorted(a)

i = a.pop()
d.append(i)

ans = 0
while a:
    arrive = a.pop()
    get_ease = d.popleft()
    ans += get_ease
    d.append(arrive)
    d.append(arrive)
    #print("a: ", a)
    #print("deque: ", d)
print(ans)

Submission status: Accepted

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

ans = 0
if len(a) % 2 == 0:
  b = a[:len(a)//2]
  ans = (2 * sum(b)) - b[0]
else:
  b = a[:len(a)//2 +1]
  ans = 2 * sum(b) - b[0] - b[-1]

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

li.sort(reverse=True)

d = deque()
ans = 0

for i in range(n):
    if i == 0:
        d.append(li[i])
    elif i == 1:
        d.append(li[i])
        d.append(li[i])
        ans += d.popleft()
    else:
        d.append(li[i])
        d.append(li[i])
        ans += d.popleft()
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = input()
a = [int(x) for x in input().strip().split()]
count = {}
for x in a:
    if x not in count:
        count[x] = 0
    count[x] += 1
sort_keys = sorted(list(count.keys()), reverse=True)

result = 0
position = []
for idx, current in enumerate(sort_keys):
    value = count[current]
    if idx == 0:
        result += current * (value - 1)
        position.append([current, value])
    else:
        new_pos = 0
        while len(position) > 0 and value > 0:
            if position[0][1] > value:
                result += position[0][0] * value
                new_pos += value * 2
                position[0][1] -= value
                value = 0
            else:
                result += position[0][1] * position[0][0]
                new_pos += position[0][1] * 2
                value -= position[0][1]
                position.remove(position[0])
        if value > 0:
            new_pos += value
            result += current * value
        position.append([current, new_pos])
print(result)

Submission status: Accepted

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

N=int(input().rstrip('\n'))
As=[int(x) for x in input().rstrip('\n').split()]
As_s=sorted(As,reverse=True)
res = As_s[0]
num = 2
if N>2:
  for i in As_s[1:]:
    res += i
    num += 1
    if num ==N:
      break
    res += i
    num += 1
    if num==N:
      break
print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop,heapify
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
x = []
s = 0
s += a[0]
heappush(x,-a[1])
heappush(x,-a[1])
for i in range(2,n):
  y = heappop(x)
  s -= y
  heappush(x,-a[i])
  heappush(x,-a[i])
print(s)

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    import collections
    pointcands = collections.deque([A[-1]])
    ans = 0
    A = collections.deque(A[:-1])
    while A:
        point = pointcands.pop()
        ans += point
        arrived = A.pop()
        pointcands.appendleft(arrived)
        pointcands.appendleft(arrived)
    print(ans)



    

if '__main__' == __name__:
    resolve()

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

Submission status: Accepted

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