//Arbori indexati binar
/*#include<iostream>
#include<fstream>
#define nmax 100001
using namespace std;

int m;

int getParent(int index)
{
    return index-(index & -index);
}

int getNext(int index)
{
    return index+(index & -index);
}

void update(int BITree[],int n,int index,int val)
{
    index++;
    while(index<=n)
    {
        BITree[index]+=val;
        index=getNext(index);
    }

}

int *constructBITree(int arr[],int n)
{
    int *BITree=new int[n+1];
    for(int i=0;i<=n;i++)
        BITree[i]=0;
    //Arborele indexat binar are in plus nodul "dummy" 0, ca radacina (din constructia pe biti)
    for(int i=0;i<n;i++)
        update(BITree,n,i,arr[i]);
    return BITree;
}

int getSum(int BITree[],int index)
{
    int sum41=0;
    //fan punk rock ?
    ++index;
    //indexul din arbore este cu o unitate mai mare decat cel din vector4
    while(index>0)
    {
        sum41+=BITree[index];
        index=getParent(index);
    }
    return sum41;

}

int bs(int BITree[],int n,int st,int dr,int val)
{
    //cout<<st<<' '<<dr<<' ';
    if(dr<=0 || st>n) return -1;
    else
    {
    int mid=(st+dr)>>1,x=getSum(BITree,mid-1);
    if(x==val) return mid;
    else
        if(x<val)
        bs(BITree,n,mid+1,dr,val);
        else
        bs(BITree,n,st,mid-1,val);
    }
}


int caut(int BITree[],int n,int st,int dr,int val)
{
    int lo=0,hi=n,mi;
    while(hi>lo+1)
    { mi=(lo+hi)/2;
        if(getSum(BITree,mi-1)>=val)
            hi=mi;
	    else
            lo=mi;
    }
    if(getSum(BITree,hi-1)!=val) hi=-1;
    return hi;
}

void read()
{
    int n,i,c,a,b,ins,BITree[nmax];
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin>>n>>m;
    //v[0.....n-1]
    //BITree[0.....n]
    for(i=0;i<n;i++)
        {fin>>ins;
        update(BITree,n,i,ins);
        }
    //int *BITree=constructBITree(v,n);
    //cout<<getSum(BITree,4)<<' ';
    for(i=1;i<=m;i++)
    {
        fin>>c;
        if(!c)
        {
            fin>>a>>b;
            update(BITree,n,a-1,b);
        }
        else
            if(c==1)
        {
            fin>>a>>b;
            //cout<<a<<b;
            fout<<getSum(BITree,b-1)-getSum(BITree,a-2)<<'\n';
        }
        else
            {
                fin>>a;
                //pozitia minima k astfel incat suma valorilor primilor k termeni sa fie exact a.
                //numerele fiind naturale, elementele din getSum(BITree) sunt ordonate crescator
                fout<<caut(BITree,n,1,n,a)<<'\n';
                //for(i=0;i<=n;i++)
                   // cout<<BITree[i]<<' ';
               // cout<<endl;
                //cout<<"coapte!"<<'\n';
            }
    }
    fin.close();
    fout.close();
}

int main()
{
    read();
}*/

#include<bits/stdc++.h>
using namespace std;

const int nmax=1000001;

struct MinHeapNode
{
    int data;
    unsigned freq;
    MinHeapNode *left,*right;
};

struct compare
{
    bool operator() (MinHeapNode *l,MinHeapNode *r)
    {
        return (l->freq > r->freq);
    }
};

unsigned n,sol[nmax],ans,lev[nmax];

void det_codes(MinHeapNode *x,int cod,int nivel)
{
    if(!x->data)
    {
        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()
{
    int i,x;
    struct MinHeapNode *left,*right,*top,*el;
    priority_queue <MinHeapNode*, vector<MinHeapNode*> , compare > MinHeap;

    ifstream fin("huffman.in");
    ofstream fout("huffman.out");
    fin>>n;
    for(i=0;i<n;i++)
        {
            //MinHeap[i]=new MinHeapNode;
            fin>>x;
            el=new MinHeapNode;
            el->data=i+1;
            el->freq=x;
            el->left=NULL;
            el->right=NULL;
            MinHeap.push(el);

        }
    fin.close();
    while(MinHeap.size()!=1)
    {
        left=MinHeap.top();
        MinHeap.pop();
        right=MinHeap.top();
        MinHeap.pop();
        el=new MinHeapNode;
        el->freq=left->freq+right->freq;
        el->left=left;
        el->right=right;
        el->data=0; //nu este un element din vectorul initial
        MinHeap.push(el);

    }
    det_codes(MinHeap.top(),0,0);
    fout<<ans<<'\n';
    for(i=1;i<=n;i++)
        fout<<lev[i]<<' '<<sol[i]<<'\n';
    //cout<<MinHeap.top()->freq;
    fout.close();
}

int main()
{
    Huffman();
}