#include<iostream>
#include<fstream>
#include<map>
#include<stdlib.h>
#define nmax 1000000

using namespace std;

class QueueNod
{
public:
     long  data;
     long  freq;
    QueueNod *left,*right;
};

class Queue
{
public:
     long  inc,sf;
     long  cap;
    QueueNod *v[nmax];
};

long  n,lev[nmax];

int isFull(Queue *q)
{
    return q->sf==q->cap-1;
    //fiind indexate de la 0 cozile
}

int isEmpty(Queue *q)
{
    return q->inc==-1;
}

int isSizeOne(Queue *q)
{
    return (q->inc==q->sf && q->inc!=-1);
}

QueueNod* dequeue(Queue *q)
{
    if(isEmpty(q))
        return NULL;
    QueueNod* el;
    el=q->v[q->inc];
    //tratez cazul in care a mai ramas un singur element in coada
    if(q->inc>=q->sf)
        {q->inc=-1;
        q->sf=-1;}
    else q->inc++;
    return el;
}


QueueNod *FindMin(Queue *fq, Queue *sq)
{
    if(isEmpty(fq))
        return dequeue(sq);
    if(isEmpty(sq))
        return dequeue(fq);
    if(fq->v[fq->inc]->freq < sq->v[sq->inc]->freq)
        return dequeue(fq);
    else return dequeue(sq);

}

long long ans;
long  sol[nmax];

/*void getCodes(QueueNod *root, string str,int nivel)
{
    if(root==NULL)
        return;
    if(root->data!=-1)
        {
        codes[root->data]=str;
        ans+=root->freq*nivel;
        lev[root->data]=nivel;
        }
        getCodes(root->left,str+"0",nivel+1);
        getCodes(root->right,str+"1",nivel+1);

}*/

void det_codes(QueueNod *x,int cod,int nivel)
{
    if(x->data<=0)
    {   det_codes(x->left,2*cod,nivel+1);
        det_codes(x->right,2*cod+1,nivel+1);
    }
    else
    {   sol[x->data]=cod;
        lev[x->data]=nivel;
        ans+=(x->freq)*nivel;
    }
}

void Huffman()
{
    long i,x;
    QueueNod *left,*right,*el;
    left=new QueueNod;
    right=new QueueNod;

    ifstream fin("huffman.in");
    ofstream fout("huffman.out");

    fin>>n;

    Queue *FirstQueue, *SecondQueue;
    //indexate de la 0
    FirstQueue=new Queue;
    FirstQueue->sf=-1;
    FirstQueue->inc=0;
    FirstQueue->cap=n;
    for(i=0;i<n;i++) FirstQueue->v[i]=new QueueNod;


    for(i=0;i<n;i++)
        {
            //MinHeap[i]=new MinHeapNode;
            fin>>x;
            el=new QueueNod;
            el->data=i+1;
            el->freq=x;
            el->left=NULL;
            el->right=NULL;
            FirstQueue->v[++FirstQueue->sf]=el;

        }
        //cout<<FirstQueue->v[0]->freq;
    SecondQueue=new Queue;
    SecondQueue->sf=-1;
    SecondQueue->inc=-1;
    SecondQueue->cap=n;
    for(i=0;i<n;i++) SecondQueue->v[i]=new QueueNod;

    //cout<<FirstQueue->v[0]->freq<<' '<<SecondQueue->v[SecondQueue->inc]->freq;
    //cout<<FindMin(FirstQueue,SecondQueue)->freq;

    while(!(isEmpty(FirstQueue) && isSizeOne(SecondQueue)))
    {
        //cout<<isSizeOne(SecondQueue)<<' ';
        left=FindMin(FirstQueue,SecondQueue);
        //cout<<left->freq<<' ';
        right=FindMin(FirstQueue,SecondQueue);
        //cout<<right->freq<<endl;
        el=new QueueNod;
        el->left=left;
        el->right=right;
        el->data=-1;
        el->freq=left->freq+right->freq;
        if(SecondQueue->inc==-1) SecondQueue->inc=0;
        SecondQueue->v[++SecondQueue->sf]=el;
        //cout<<FirstQueue->inc<<' '<<SecondQueue->sf<<endl;
        //cout<<el->freq<<' ';
    }
    //cout<<el->freq;
    //getCodes(el,"",0);
    //fout<<ans<<'\n';
    /*for(i=1;i<=n;i++)
    {
        string st=codes[i];
        uint64_t number;
        number = strtoull (st.c_str (),NULL,2);
        fout<<lev[i]<<' '<<number<<'\n';
    }*/
    det_codes(el,0,0);
    fout<<ans<<'\n';
    for(i=1;i<=n;i++)
        fout<<lev[i]<<' '<<sol[i]<<'\n';

}

int main()
{
    Huffman();

}