#include <fstream>
#include <vector>
#include <queue>
#define MX 1000001
using namespace std;

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

struct nod
{
    int id,frecv;
    nod *st,*dr;
};

struct cmp
{
    bool operator() (nod* a, nod* b)
    {
        return a->frecv > b->frecv;
    }
};

int n;
priority_queue<nod*, vector<nod*>, cmp> q;
int lg[MX];
long long total, sir[MX], actual;

void citire()
{
    int i;
    nod* e;
    fin>>n;
    for(i=1; i<=n; i++)
    {
        e = new nod;
        e->id = i;
        fin>>(e->frecv);
        e->st = e->dr = NULL;
        q.push(e);
    }
}

void huffman()
{
    nod *u1, *u2, *e;
    while(q.size() > 1)
    {
        u1 = q.top();
        q.pop();

        u2 = q.top();
        q.pop();

        e = new nod;
        e->id = 0;
        e->frecv = u1->frecv + u2->frecv;
        e->st = u1;
        e->dr = u2;
        q.push(e);
    }
}

void SDR(nod* p, int l)
{
    if(p)
    {
        actual = (actual<<1);
        SDR(p->st, l+1);

        actual += 1;
        SDR(p->dr, l+1);

        actual = (actual>>1);

        //fout<<l<<'\n';

        if(p->id)
        {
            sir[p->id] = actual;
            lg[p->id] = l;
        }
        else
        {
            total += p->frecv;
        }
        delete p;
    }
}

int main()
{
    citire();
    huffman();
    SDR(q.top(), 0);
    q.pop();

    fout<<total<<'\n';
    int i;
    for(i=1; i<=n; i++)
    {
        fout<<lg[i]<<' '<<sir[i]<<'\n';
    }

    fin.close(); fout.close();
    return 0;
}