# Codeforces 890 D. Boxes And Balls （哈夫曼）

## Description

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 a1, a2, …, an (1 ≤ ai ≤ 10^9), where ai 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


## Examples output

6


## 思路

• 对于 n 为奇数的情况，我们每次挑选最小的三个节点合并然后加入到队列。
• 对于 n 为偶数的情况，我们可以增加一个权值为 0 的节点转化为奇数方案。

## AC 代码

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);\
cin.tie(0);\
cout.tie(0);
using namespace std;
typedef __int64 LL;
const int maxn = 2e5+10;
const double eps = 1e-8;

priority_queue<LL,vector<LL>,greater<LL> >q;

void solve()
{
LL ans = 0;
while(q.size()>1)
{
LL tmp = 0;
for(int i=0; i<3; i++)
{
if(!q.empty())
{
tmp+=q.top();
q.pop();
}
}
q.push(tmp);
ans+=tmp;
}
cout<<ans<<endl;
}

int main()
{
IO;
int n;
cin>>n;
if(n%2==0)q.push(0);
for(int i=1; i<=n; i++)
{
LL x;
cin>>x;
q.push(x);
}
solve();
return 0;
}