#include <fstream>
#include <queue>

using namespace std;

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

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

queue <CH*> Qf,Qi;

CH* AH[2*1000001];

int n,x;

CH* Creare(int x,CH* xfs=NULL,CH* xfd=NULL,int xlg=0,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();
    Qf.pop();

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

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

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

        if(Qf.front()->va <= Qi.front()->va)
        {
            y=Qf.front();
            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();
}

int Coduri(CH* st,int lgd,int cod)
{
    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;
}

void Debg(CH* st)
{
    if(st->fs!=NULL)
    {
        cout<<"FS : "<<st->va<<' '<<st->fs->va<<'\n';
        Debg(st->fs);
    }
    if(st->fd!=NULL)
    {
        cout<<"FD : "<<st->va<<' '<<st->fd->va<<'\n';
        Debg(st->fd);
    }
}

int main()
{
    cin>>n;

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

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

    //Debg(Arbore());

    cout<<Coduri(Arbore(/*Qf,Qi*/),0,0);

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

    return 0;
}