Ivan has n different boxes. The first of them contains some balls of n different colors.

Ivan wants to play a strange game. He wants to distribute the balls into boxes in such a way that for every i (1 ≤ i ≤ n) i-th box will contain all balls with color i.

In order to do this, Ivan will make some turns. Each turn he does the following:  Ivan chooses any non-empty box and takes all balls from this box;  Then Ivan chooses any k empty boxes (the box from the first step becomes empty, and Ivan is allowed to choose it), separates the balls he took on the previous step into k non-empty groups and puts each group into one of the boxes. He should put each group into a separate box. He can choose either k = 2 or k = 3. 

The penalty of the turn is the number of balls Ivan takes from the box during the first step of the turn. And penalty of the game is the total penalty of turns made by Ivan until he distributes all balls to corresponding boxes.

Help Ivan to determine the minimum possible penalty of the game!


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 200000) — the number of boxes and colors.

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is the number of balls with color i.


-----Output-----

Print one number — the minimum possible penalty of the game.


-----Examples-----
Input
3
1 2 3

Output
6

Input
4
2 3 4 5

Output
19



-----Note-----

In the first example you take all the balls from the first box, choose k = 3 and sort all colors to corresponding boxes. Penalty is 6.

In the second example you make two turns:   Take all the balls from the first box, choose k = 3, put balls of color 3 to the third box, of color 4 — to the fourth box and the rest put back into the first box. Penalty is 14;  Take all the balls from the first box, choose k = 2, put balls of color 1 to the first box, of color 2 — to the second box. Penalty is 5. 

Total penalty is 19.

Difficulty: HARD
Tags: Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
import heapq
N = int(input())
colors = list(map(int, input().strip().split()))
if N % 2 == 0:
	colors.append(0)
penalty = 0
heapq.heapify(colors)
while len(colors) > 2:
	a = heapq.heappop(colors)
	b = heapq.heappop(colors)
	c = heapq.heappop(colors)
	heapq.heappush(colors, a + b + c)
	penalty += a + b + c
print(penalty)


import heapq
n = int(input())
heap = list(map(int, input().split())) + ([0] if n % 2 == 0 else [])
n = len(heap)
heapq.heapify(heap)
ans = 0
for i in range(n, 1, -2):
	x = heapq.heappop(heap) + heapq.heappop(heap) + heapq.heappop(heap)
	heapq.heappush(heap, x)
	ans += x
print(ans)


import heapq
input()
heap = [int(i) for i in input().split()]
heapq.heapify(heap)
cost = 0
while len(heap) > 1:
	amountToMerge = 3
	if len(heap) % 2 == 0:
		amountToMerge = 2
	mergedPileSize = 0
	for _ in range(amountToMerge):
		mergedPileSize += heapq.heappop(heap)
	cost += mergedPileSize
	heapq.heappush(heap, mergedPileSize)
print(cost)


import heapq
ip = lambda : map(int, input().split())
n = ip()
l = list(ip())
if len(l) % 2 == 0:
	l.append(0)
heapq.heapify(l)
pen = 0
while len(l) > 1:
	x = heapq.heappop(l)
	y = heapq.heappop(l)
	z = heapq.heappop(l)
	pen = pen + x + y + z
	heapq.heappush(l, x + y + z)
print(pen)


from heapq import *
n = int(input())
a = list(map(int, input().split()))
heap = []
res = 0
for i in range(n):
	heappush(heap, a[i])
if n % 2 == 0:
	heappush(heap, 0)
while n > 1:
	cur = heappop(heap)
	cur += heappop(heap)
	cur += heappop(heap)
	res += cur
	heappush(heap, cur)
	n -= 2
print(res)


from heapq import *

def score(A):
	heapify(A)
	res = 0
	if len(A) % 2 == 0:
		(a0, a1) = (heappop(A), heappop(A))
		a = a0 + a1
		res += a
		heappush(A, a)
	while len(A) > 1:
		(a0, a1, a2) = (heappop(A), heappop(A), heappop(A))
		a = a0 + a1 + a2
		res += a
		heappush(A, a)
	return res

def main():
	n = int(input())
	A = list(map(int, input().split()))
	print(score(A))
main()


import sys
from heapq import heappop, heappush, heapify
n = int(sys.stdin.buffer.readline().decode('utf-8'))
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
heapify(a)
if n <= 3:
	print(0 if n == 1 else sum(a))
	exit()

def solve(x, heap):
	cost = sum((heappop(heap) for _ in range(x)))
	heappush(heap, cost)
	while len(heap) > 1:
		c = sum((heappop(heap) for _ in range(min(3, len(heap)))))
		cost += c
		heappush(heap, c)
	return cost
print(min(solve(2, a[:]), solve(3, a[:])))


import heapq
n = int(input())
a = [int(i) for i in input().split()]
heapq.heapify(a)
if n & 1 == 0:
	heapq.heappush(a, 0)
res = 0
while len(a) > 1:
	s = heapq.heappop(a) + heapq.heappop(a) + heapq.heappop(a)
	res += s
	heapq.heappush(a, s)
print(res)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
from heapq import *
mod = 10 ** 9 + 7
md = 998244353
tc = 1
for _ in range(tc):
	(n,) = inp()
	a = inp()
	ans = 0
	if n & 1 == 0:
		a.append(0)
	heapify(a)
	while len(a) >= 3:
		temp = heappop(a) + heappop(a) + heappop(a)
		ans += temp
		heappush(a, temp)
	print(ans)


n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0:
	a.append(0)
import heapq
heapq.heapify(a)
ans = 0
while len(a) > 1:
	x = heapq.heappop(a)
	y = heapq.heappop(a)
	z = heapq.heappop(a)
	ans += x + y + z
	heapq.heappush(a, x + y + z)
print(ans)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
N = int(input())
A = [int(x) for x in input().split()]
if N % 2 == 0:
	A.append(0)
heapq.heapify(A)
ans = 0
while len(A) > 1:
	i = 0
	p = 0
	while A and i < 3:
		p += heapq.heappop(A)
		i += 1
	heapq.heappush(A, p)
	ans += p
print(ans)


import heapq
n = input()
A = list(map(int, input().split()))
if len(A) % 2 == 0:
	A.append(0)
st = 0
heapq.heapify(A)
while len(A) > 1:
	abc = 0
	a = heapq.heappop(A)
	b = heapq.heappop(A)
	c = heapq.heappop(A)
	abc = a + b + c
	st = st + abc
	heapq.heappush(A, abc)
print(st)


import heapq

def solve(heap, n):
	heapq.heapify(heap)
	ans = 0
	while n > 1:
		x = heapq.heappop(heap)
		y = heapq.heappop(heap)
		z = heapq.heappop(heap)
		heapq.heappush(heap, x + y + z)
		ans += x + y + z
		n -= 2
	return ans
n = int(input())
a = list(map(int, input().split()))
a.sort()
if n % 2 == 0:
	delta = a[0] + a[1]
	a = [delta] + a[2:]
	n -= 1
	print(solve(a, n) + delta)
else:
	print(solve(a, n))


import heapq as h
n = int(input())
line2 = input().split()
a = []
for i in range(n):
	h.heappush(a, int(line2[i]))
if n == 1:
	print(0)
else:
	result = 0
	if n % 2 == 1:
		k = n
	else:
		a.append(0)
		k = n + 1
	while k > 3:
		previous = h.heappop(a) + h.heappop(a) + h.heappop(a)
		result += previous
		h.heappush(a, previous)
		k -= 2
	result += sum(a)
	print(result)


import heapq
n = int(input())
resp = 0
test = [int(i) for i in input().split()]
test.sort()
if n % 2 == 0:
	test = [0] + test
	n += 1
while n != 1:
	c = heapq.heappop(test) + heapq.heappop(test) + heapq.heappop(test)
	resp += c
	heapq.heappush(test, c)
	n -= 2
print(resp)


import heapq
n = int(input())
lst = list(map(int, input().strip().split()))
if n % 2 == 0:
	lst.append(0)
penalty = 0
heapq.heapify(lst)
while len(lst) > 1:
	a = heapq.heappop(lst)
	b = heapq.heappop(lst)
	c = heapq.heappop(lst)
	penalty += a + b + c
	heapq.heappush(lst, a + b + c)
print(penalty)


import heapq as h
n = int(input())
a = [int(x) for x in input().split()]
if len(a) % 2 == 0:
	a.append(0)
h.heapify(a)
ans = 0
while len(a) > 1:
	a1 = h.heappop(a)
	a2 = h.heappop(a)
	a3 = h.heappop(a)
	ans += a1 + a2 + a3
	h.heappush(a, a1 + a2 + a3)
print(ans)


import heapq
n = int(input())
l = [int(i) for i in input().split()]
if n % 2 == 0:
	l = [0] + l
result = 0
heapq.heapify(l)
while len(l) > 1:
	x = heapq.heappop(l)
	y = heapq.heappop(l)
	z = heapq.heappop(l)
	result += x + y + z
	heapq.heappush(l, x + y + z)
print(result)


from heapq import *
n = int(input())
a = list(map(int, input().split()))
s = 0
if len(a) % 2 == 0:
	a = [0] + a
	n += 1

def sc(a, s=0):
	heapify(a)
	for i in range((n - 1) // 2):
		k = heappop(a) + heappop(a) + heappop(a)
		s += k
		heappush(a, k)
	print(s)
sc(a)


import heapq as h
n = int(input())
ai = [int(i) for i in input().split()]
if n % 2 == 0:
	ai = [0] + ai
result = 0
h.heapify(ai)
while len(ai) > 1:
	a1 = h.heappop(ai)
	a2 = h.heappop(ai)
	a3 = h.heappop(ai)
	result += a1 + a2 + a3
	h.heappush(ai, a1 + a2 + a3)
print(result)


import os, sys, bisect, copy
from heapq import heappush as pus, heappop as pp, heapify
from collections import defaultdict, Counter, deque
from functools import lru_cache
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

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

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
n = int(input())
a = list(mapi())
a.sort()
heapify(a)
res = 0
if n % 2 == 0:
	pus(a, 0)
while len(a) > 1:
	if len(a) >= 3:
		tmp = pp(a) + pp(a) + pp(a)
		res += tmp
		pus(a, tmp)
	elif len(a) == 2:
		tmp = pp(a) + pp(a)
		res += tmp
		pus(a, tmp)
print(res)


import heapq
n = int(input())
colors_lens = list(map(int, input().split()))
if len(colors_lens) % 2 == 0:
	colors_lens.append(0)
heapq.heapify(colors_lens)
ans = 0
l = len(colors_lens)
while l > 1:
	su = 0
	su += heapq.heappop(colors_lens)
	su += heapq.heappop(colors_lens)
	su += heapq.heappop(colors_lens)
	ans += su
	heapq.heappush(colors_lens, su)
	l -= 2
print(ans)


import heapq
n = int(input())
array = input().split()
fin = []
for i in array:
	fin.append(int(i))
if len(fin) % 2 == 0:
	fin.append(0)
heapq.heapify(fin)
sums = 0
while len(fin) > 1:
	temp = 0
	a = heapq.heappop(fin)
	b = heapq.heappop(fin)
	c = heapq.heappop(fin)
	temp = a + b + c
	sums += temp
	heapq.heappush(fin, temp)
print(sums)


class heap:

	def __init__(self, maxn):
		self.a = [0] * maxn
		self.size = 0

	def shift_down(self, i):
		while 2 * i + 1 < self.size:
			l = 2 * i + 1
			r = 2 * i + 2
			j = l
			if r < self.size and self.a[r] < self.a[l]:
				j = r
			if self.a[i] <= self.a[j]:
				break
			(self.a[i], self.a[j]) = (self.a[j], self.a[i])
			i = j

	def shift_up(self, i):
		while i and self.a[i] < self.a[(i - 1) // 2]:
			(self.a[i], self.a[(i - 1) // 2]) = (self.a[(i - 1) // 2], self.a[i])
			i = (i - 1) // 2

	def erase_min(self):
		mn = self.a[0]
		self.a[0] = self.a[self.size - 1]
		self.size -= 1
		self.shift_down(0)
		return mn

	def insert(self, val):
		self.size += 1
		self.a[self.size - 1] = val
		self.shift_up(self.size - 1)
n = int(input())
ans = 0
s = heap(400000 + 100)
for i in [int(j) for j in input().split()]:
	s.insert(i)
if s.size % 2 == 0:
	s.insert(0)
while s.size > 1:
	t = s.erase_min() + s.erase_min()
	if s.size:
		t += s.erase_min()
	ans += t
	s.insert(t)
print(ans)


r = lambda : map(int, input().split())
import heapq

def main():
	(n,) = r()
	a = list(r())
	if len(a) % 2 == 0:
		a.append(0)
	heapq.heapify(a)
	ret = 0
	while len(a) > 1:
		x = heapq.heappop(a)
		y = heapq.heappop(a)
		z = heapq.heappop(a)
		ret += x + y + z
		heapq.heappush(a, x + y + z)
	print(ret)
main()