//Coduri Huffman

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

const unsigned long long nmax=1000001;

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

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

unsigned long long 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;
    }
}

map<int, string> codes;

void getCodes(MinHeapNode *root, string str,int nivel)
{
    if(root==NULL)
        return;
    if(root->data)
        {
        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 Huffman()
{
    unsigned long long 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);

    }
    getCodes(MinHeap.top(),"",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(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();
}