#include <fstream>
#include <queue>

using namespace std;

ifstream cin("huffman.in");
ofstream cout("huffman.out");

struct CH
{
    long long int va;
    long long int lg;
    long long int cd;
    CH* fs;
    CH* fd;
};

queue <CH*> Qf,Qi,AH;

int n,x,conto;

CH* Creare(long long int x,CH* xfs=NULL,CH* xfd=NULL,long long int xlg=0,long long int xcd=0)
{
    CH* p=new CH;
    p->va=x;
    p->fs=xfs;
    p->fd=xfd;
    p->lg=xlg;
    p->cd=xcd;

    return p;
}

CH* Arbore(queue <CH*> Qf,queue <CH*> Qi)
{
    CH* x;
    CH* y;

    x=Qf.front();
    AH.push(x);
    Qf.pop();

    y=Qf.front();
    AH.push(y);
    Qf.pop();

    Qi.push(Creare(x->va+y->va,x,y));

    while(Qf.size())
    {
        if(Qf.front()->va <= Qi.front()->va)
        {
            x=Qf.front();
            AH.push(x);
            Qf.pop();
        }
        else
        {
            x=Qi.front();
            Qi.pop();
        }

        if(!Qf.empty())
        {
            if(!Qi.empty())
            {
                if(Qf.front()->va <= Qi.front()->va)
                {
                    y=Qf.front();
                    AH.push(y);
                    Qf.pop();
                }
                else
                {
                    y=Qi.front();
                    Qi.pop();
                }
            }
            else
            {
                y=Qf.front();
                AH.push(y);
                Qf.pop();
            }
        }
        else
        {
            y=Qi.front();
            Qi.pop();
        }

        Qi.push(Creare(x->va+y->va,x,y));
    }

    while(Qi.size()!=1)
    {
        x=Qi.front();
        Qi.pop();

        y=Qi.front();
        Qi.pop();

        Qi.push(Creare(x->va+y->va,x,y));
    }

    return Qi.front();
}

long long int Coduri(CH* st,long long int lgd,long long int cod)
{
    long long int sum=0;

    if(st->fs!=NULL && st->fd!=NULL)
        sum=st->va;

    st->cd=cod;
    st->lg=lgd;

    //cout<<st->va<<' '<<cod<<'\n';

    if(st->fs!=NULL)
        sum+=Coduri(st->fs,lgd+1,cod*2);

    if(st->fd!=NULL)
        sum+=Coduri(st->fd,lgd+1,(cod*2)+1);

    return sum;
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;++i)
    {
        cin>>x;

        Qf.push(/*AH[i]=*/Creare(x));
    }

    cout<<Coduri(Arbore(Qf,Qi),0,0)<<'\n';

    /*for(int i=1;i<=n;++i)
        cout<<AH[i]->lg<<' '<<AH[i]->cd<<'\n';*/

    while(!AH.empty())
    {
        cout<<AH.front()->lg<<' '<<AH.front()->cd<<'\n';
        AH.pop();
    }

    return 0;
}