#include <fstream>
#include <queue>

using namespace std;

const int nmax = 1000005;

struct nod
{
    nod *left, *right;
    int index, weight;
} *min1, *min2;

long long code[nmax];
int depth[nmax];
queue < nod* > Q1,Q2;

inline nod* getMin()
{
    nod *x;
    if (Q2.empty())
    {
        x=Q1.front();
        Q1.pop();
        return x;
    }
    else if (Q1.empty())
    {
        x=Q2.front();
        Q2.pop();
        return x;
    }
    else
    {
        if (Q1.front()->weight<Q2.front()->weight)
        {
            x=Q1.front();
            Q1.pop();
        }
        else
        {
            x=Q2.front();
            Q2.pop();
        }
        return x;
    }
}

void df(nod *x, int code_size, long long code_value)
{
    if (x->index)
    {
        depth[x->index]=code_size;
        code[x->index]=code_value;
        return;
    }
    df(x->left, code_size+1, code_value<<1);
    df(x->right, code_size+1, (code_value<<1)+1);
}

int main()
{
    ifstream f("huffman.in");
    ofstream g("huffman.out");
    int n,w;
    f>>n;
    for (int i=1; i<=n; ++i)
    {
        f>>w;
        nod *x;
        x = new nod;
        x->index=i;
        x->weight=w;
        x->left=x->right=NULL;
        Q1.push(x);
    }
    int k=0, internal_weight=0;
    while (k<n-1)
    {
        ++k;
        min1=getMin();
        min2=getMin();
        nod *x;
        x = new nod;
        x->left=min1;
        x->right=min2;
        x->weight=min1->weight+min2->weight;
        x->index=0;
        Q2.push(x);
        internal_weight+=x->weight;
    }
    nod *root = getMin();
    df(root,0,0);

    g<<internal_weight<<'\n';

    for (int i=1; i<=n; ++i)
        g<<depth[i]<<' '<<code[i]<<'\n';

    return 0;
}