#include <iostream>
#include <fstream>

using namespace std;

struct Nod
{
    int numarAparitii;
    int fiu[2];
};

const int numarMaximSimboluri = 1000000;
struct Coada
{
    int indice[numarMaximSimboluri];
    int inceput;
    int sfarsit;
    void initializeaza()
    {
        inceput = 0;
        sfarsit = -1;
    }
    void adauga(int i)
    {
        sfarsit++;
        indice[sfarsit] = i;
    }
    bool esteGoala()
    {
        return inceput > sfarsit;
    }
    int i()
    {
        return indice[inceput];
    }
    int scoate()
    {
        int deIntors = indice[inceput];
        inceput++;
        return deIntors;
    }
    bool areUnSingurElement()
    {
        return inceput == sfarsit;
    }
};

Coada coadaNoduriInitiale;
Coada coadaNoduriInterne;

int celMaiMicNod(Nod nod[])
{
    if(coadaNoduriInterne.esteGoala())
        return coadaNoduriInitiale.scoate();
    else if(coadaNoduriInitiale.esteGoala())
        return coadaNoduriInterne.scoate();
    else if(nod[coadaNoduriInitiale.i()].numarAparitii < nod[coadaNoduriInterne.i()].numarAparitii)
        return coadaNoduriInitiale.scoate();
    else
        return coadaNoduriInterne.scoate();
}

long long lungimeMinima;
int nodIntern(Nod nod[], int &numarNoduri)
{
    Nod nodNou;
    nodNou.fiu[0] = celMaiMicNod(nod);
    nodNou.fiu[1] = celMaiMicNod(nod);
    cout << nod[nodNou.fiu[0]].numarAparitii << ' ' << nod[nodNou.fiu[1]].numarAparitii << '\n';
    nodNou.numarAparitii = nod[nodNou.fiu[0]].numarAparitii + nod[nodNou.fiu[1]].numarAparitii;
    lungimeMinima += nodNou.numarAparitii;
    nod[numarNoduri] = nodNou;
    int deIntors = numarNoduri;
    numarNoduri++;
    return deIntors;
}

void construiesteNoduriInterne(Nod nod[], int &numarNoduri)
{
    while(coadaNoduriInitiale.inceput + coadaNoduriInterne.inceput <= coadaNoduriInitiale.sfarsit + coadaNoduriInterne.sfarsit)
        coadaNoduriInterne.adauga(nodIntern(nod, numarNoduri));
}

int lungimeCod[numarMaximSimboluri];
long long cod[numarMaximSimboluri];
void parcurgereInAdancime(Nod nod[], int i, int adancime, long long codZecimal)
{
    if(nod[i].fiu[0] != -1)
    {
        parcurgereInAdancime(nod, nod[i].fiu[0], adancime+1, codZecimal*2);
        parcurgereInAdancime(nod, nod[i].fiu[1], adancime+1, codZecimal*2+1);
        return;
    }
    lungimeCod[i] = adancime;
    cod[i] = codZecimal;
}

int main()
{
    int numarSimboluri;
    ifstream fin("huffman.in");
    fin >> numarSimboluri;
    coadaNoduriInitiale.initializeaza();
    Nod nod[2*numarSimboluri - 1];
    for(int i=0; i<numarSimboluri; i++)
    {
        fin >> nod[i].numarAparitii;
        nod[i].fiu[0] = -1;
        nod[i].fiu[1] = -1;
        coadaNoduriInitiale.adauga(i);
    }
    coadaNoduriInterne.initializeaza();
    int numarNoduri = numarSimboluri;
    construiesteNoduriInterne(nod, numarNoduri);
    cout<<lungimeMinima;
    parcurgereInAdancime(nod, coadaNoduriInterne.scoate(), 0, 0);
    ofstream fout("huffman.out");
    fout << lungimeMinima << '\n';
    for(int i=0; i<numarSimboluri; i++)
        fout << lungimeCod[i] << ' ' << cod[i] << '\n';
    return 0;
}