#include <iostream>
#include <fstream>
#include <queue>

class Nod {
public:
    int indexChr;
    int frecv;
    Nod* dr;
    Nod* st;
};

class compara {
public:
    int operator()(const Nod* nod1, const Nod* nod2) {
        return nod1->frecv > nod2->frecv;
    }
};

void func(Nod* rad, int k, int st[], int vBiti[], int vCod[], long long int &t) {
    if(!rad)
        return;

    if(rad->indexChr != -1) {
        int index = rad->indexChr;
        vBiti[index] = k;
        t += k * rad->frecv;

        int copie = k-1;
        int b = 1;

        while(copie >= 0) {
            vCod[index] += st[copie] * b;
            b *= 2;
            copie--;
        }

        return;
    }

    st[k] = 0;
    func(rad->st, k+1, st, vBiti, vCod, t);

    st[k] = 1;
    func(rad->dr, k+1, st, vBiti, vCod, t);

}
int main() {
    std::ifstream f("grader_test7.in");
    std::ofstream g("huffman.out");

    std::priority_queue <Nod*, std::vector<Nod*>, compara> minList;

    int n;
    f >> n;
    int frecv;
    Nod* nod_aux = nullptr;
    for(int i = 0; i < n; i++) {
        f >> frecv;
        nod_aux = new Nod;
        nod_aux->indexChr = i;
        nod_aux->frecv = frecv;
        minList.push(nod_aux);
    }

    Nod* nod1 = nullptr;
    Nod* nod2 = nullptr;

    while (minList.size() > 1) {
        nod1 = minList.top();
        minList.pop();
        nod2 = minList.top();
        minList.pop();
        nod_aux = new Nod;
        nod_aux->indexChr = -1;
        nod_aux->frecv = nod1->frecv + nod2->frecv;
        nod_aux->dr = nod2;
        nod_aux->st = nod1;
        minList.push(nod_aux);
    }

    int nrBiti[n];
    int codbinar[n];

    for(int i = 0; i < n; i++)
        codbinar[i] = 0;

    int stivaPracurgere[n/2];
    long long int total = 0;

    func(minList.top(), 0, stivaPracurgere, nrBiti, codbinar, total);

    g << total << "\n";

    for(int i = 0; i < n; i++)
        g << nrBiti[i] << " " << codbinar[i] << "\n";

    return 0;
}