#include <bits/stdc++.h>
using namespace std;
ifstream f ("huffman.in");
ofstream g ("huffman.out");
#define maxn 1000000
#define maxv 100000000
int fr1=0, fr2=0, bk1=-1, bk2=-1, n;
struct node
{
    long long val;
    node *left, *right;
};
node* root;
vector < pair <node*, long long> > q1;
vector <pair <node*, long long> > q2;
string s;
node* new_node(long long val)
{
    node* temp=new node;
    temp->val=val;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

void push(int i, node* a, long long val)
{
    if(i==1)
    {
        bk1++;
        q1.push_back(make_pair(a, val));
    }
    else if(i==2)
    {
        bk2++;
        q2.push_back(make_pair(a, val));
    }
}

pair<node*, long long> top(int i)
{
    if(i==1)
        return q1[fr1];
    else if (i==2)
        return q2[fr2];
}

pair<node*, long long> pretop(int i)
{
    if(i==1)
        return q1[fr1+1];
    else if (i==2)
        return q2[fr2+1];
}

void pop(int i)
{
    if(i==1)
        fr1++;
    else if(i==2)
        fr2++;
}





int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        int x;
        f>>x;
        node* a=new_node(x);
        push(1, a, x);
    }
    int val=top(1).second+ pretop(1).second;
    node* a=new_node(val);
    a->left=top(1).first;
    a->right=pretop(1).first;
    push(2,a, val);
    pop(1);
    pop(1);

    while(bk1-fr1+1 + bk2-fr2+1 >=2)
    {
        ///daca iau 2 din sk1
        ///daca iau 2 din sk2
        ///daca iau 1 din sk1 si 1 din sk2
        long long v1, v2, v3;
        if(bk1>fr1)
        {
            v1=top(1).second+pretop(1).second;
        }
        else
        {
            v1=maxn*maxv+100;
        }
        if(bk2>fr2)
        {
            v2=top(2).second+pretop(2).second;
        }
        else
        {

            v2=maxn*maxv+100;
        }
        v3=top(1).second+top(2).second;
        //cout<<v1<<" "<<v2<<" "<<v3<<"\n";
        //cout<<fr1<<" "<<fr2<<" "<<bk1<<" "<<bk2<<"\n";
        if(v1==min(min(v1, v2),v3))
        {
            node* a=new_node(v1);
            a->left=top(1).first;
            a->right=pretop(1).first;
            root=a;
            push(2, a, v1);
            pop(1);
            pop(1);
        }
        else if(v2==min(min(v1, v2),v3))
        {
            node* a=new_node(v2);
            a->left=top(2).first;
            a->right=pretop(2).first;
            root=a;
            push(2, a, v2);
            pop(2);
            pop(2);
        }
        else
        {
            node* a=new_node(v3);
            a->left=top(1).first;
            a->right=pretop(2).first;
            root=a;
            push(2, a, v3);
            pop(1);
            pop(2);
        }
    }
    //dfs(root);
    return 0;
}